1 /* 2 ** $Id: lgc.c,v 2.140.1.3 2014/09/01 16:55:08 roberto Exp $ 3 ** Garbage Collector 4 ** See Copyright Notice in lua.h 5 */ 6 7 #define lgc_c 8 #define LUA_CORE 9 10 #include <sys/lua/lua.h> 11 12 #include "ldebug.h" 13 #include "ldo.h" 14 #include "lfunc.h" 15 #include "lgc.h" 16 #include "lmem.h" 17 #include "lobject.h" 18 #include "lstate.h" 19 #include "lstring.h" 20 #include "ltable.h" 21 #include "ltm.h" 22 23 24 25 /* 26 ** cost of sweeping one element (the size of a small object divided 27 ** by some adjust for the sweep speed) 28 */ 29 #define GCSWEEPCOST ((sizeof(TString) + 4) / 4) 30 31 /* maximum number of elements to sweep in each single step */ 32 #define GCSWEEPMAX (cast_int((GCSTEPSIZE / GCSWEEPCOST) / 4)) 33 34 /* maximum number of finalizers to call in each GC step */ 35 #define GCFINALIZENUM 4 36 37 38 /* 39 ** macro to adjust 'stepmul': 'stepmul' is actually used like 40 ** 'stepmul / STEPMULADJ' (value chosen by tests) 41 */ 42 #define STEPMULADJ 200 43 44 45 /* 46 ** macro to adjust 'pause': 'pause' is actually used like 47 ** 'pause / PAUSEADJ' (value chosen by tests) 48 */ 49 #define PAUSEADJ 100 50 51 52 /* 53 ** 'makewhite' erases all color bits plus the old bit and then 54 ** sets only the current white bit 55 */ 56 #define maskcolors (~(bit2mask(BLACKBIT, OLDBIT) | WHITEBITS)) 57 #define makewhite(g,x) \ 58 (gch(x)->marked = cast_byte((gch(x)->marked & maskcolors) | luaC_white(g))) 59 60 #define white2gray(x) resetbits(gch(x)->marked, WHITEBITS) 61 #define black2gray(x) resetbit(gch(x)->marked, BLACKBIT) 62 63 64 #define isfinalized(x) testbit(gch(x)->marked, FINALIZEDBIT) 65 66 #define checkdeadkey(n) lua_assert(!ttisdeadkey(gkey(n)) || ttisnil(gval(n))) 67 68 69 #define checkconsistency(obj) \ 70 lua_longassert(!iscollectable(obj) || righttt(obj)) 71 72 73 #define markvalue(g,o) { checkconsistency(o); \ 74 if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); } 75 76 #define markobject(g,t) { if ((t) && iswhite(obj2gco(t))) \ 77 reallymarkobject(g, obj2gco(t)); } 78 79 static void reallymarkobject (global_State *g, GCObject *o); 80 81 82 /* 83 ** {====================================================== 84 ** Generic functions 85 ** ======================================================= 86 */ 87 88 89 /* 90 ** one after last element in a hash array 91 */ 92 #define gnodelast(h) gnode(h, cast(size_t, sizenode(h))) 93 94 95 /* 96 ** link table 'h' into list pointed by 'p' 97 */ 98 #define linktable(h,p) ((h)->gclist = *(p), *(p) = obj2gco(h)) 99 100 101 /* 102 ** if key is not marked, mark its entry as dead (therefore removing it 103 ** from the table) 104 */ 105 static void removeentry (Node *n) { 106 lua_assert(ttisnil(gval(n))); 107 if (valiswhite(gkey(n))) 108 setdeadvalue(gkey(n)); /* unused and unmarked key; remove it */ 109 } 110 111 112 /* 113 ** tells whether a key or value can be cleared from a weak 114 ** table. Non-collectable objects are never removed from weak 115 ** tables. Strings behave as `values', so are never removed too. for 116 ** other objects: if really collected, cannot keep them; for objects 117 ** being finalized, keep them in keys, but not in values 118 */ 119 static int iscleared (global_State *g, const TValue *o) { 120 if (!iscollectable(o)) return 0; 121 else if (ttisstring(o)) { 122 markobject(g, rawtsvalue(o)); /* strings are `values', so are never weak */ 123 return 0; 124 } 125 else return iswhite(gcvalue(o)); 126 } 127 128 129 /* 130 ** barrier that moves collector forward, that is, mark the white object 131 ** being pointed by a black object. 132 */ 133 void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) { 134 global_State *g = G(L); 135 lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o)); 136 lua_assert(g->gcstate != GCSpause); 137 lua_assert(gch(o)->tt != LUA_TTABLE); 138 if (keepinvariantout(g)) /* must keep invariant? */ 139 reallymarkobject(g, v); /* restore invariant */ 140 else { /* sweep phase */ 141 lua_assert(issweepphase(g)); 142 makewhite(g, o); /* mark main obj. as white to avoid other barriers */ 143 } 144 } 145 146 147 /* 148 ** barrier that moves collector backward, that is, mark the black object 149 ** pointing to a white object as gray again. (Current implementation 150 ** only works for tables; access to 'gclist' is not uniform across 151 ** different types.) 152 */ 153 void luaC_barrierback_ (lua_State *L, GCObject *o) { 154 global_State *g = G(L); 155 lua_assert(isblack(o) && !isdead(g, o) && gch(o)->tt == LUA_TTABLE); 156 black2gray(o); /* make object gray (again) */ 157 gco2t(o)->gclist = g->grayagain; 158 g->grayagain = o; 159 } 160 161 162 /* 163 ** barrier for prototypes. When creating first closure (cache is 164 ** NULL), use a forward barrier; this may be the only closure of the 165 ** prototype (if it is a "regular" function, with a single instance) 166 ** and the prototype may be big, so it is better to avoid traversing 167 ** it again. Otherwise, use a backward barrier, to avoid marking all 168 ** possible instances. 169 */ 170 LUAI_FUNC void luaC_barrierproto_ (lua_State *L, Proto *p, Closure *c) { 171 global_State *g = G(L); 172 lua_assert(isblack(obj2gco(p))); 173 if (p->cache == NULL) { /* first time? */ 174 luaC_objbarrier(L, p, c); 175 } 176 else { /* use a backward barrier */ 177 black2gray(obj2gco(p)); /* make prototype gray (again) */ 178 p->gclist = g->grayagain; 179 g->grayagain = obj2gco(p); 180 } 181 } 182 183 184 /* 185 ** check color (and invariants) for an upvalue that was closed, 186 ** i.e., moved into the 'allgc' list 187 */ 188 void luaC_checkupvalcolor (global_State *g, UpVal *uv) { 189 GCObject *o = obj2gco(uv); 190 lua_assert(!isblack(o)); /* open upvalues are never black */ 191 if (isgray(o)) { 192 if (keepinvariant(g)) { 193 resetoldbit(o); /* see MOVE OLD rule */ 194 gray2black(o); /* it is being visited now */ 195 markvalue(g, uv->v); 196 } 197 else { 198 lua_assert(issweepphase(g)); 199 makewhite(g, o); 200 } 201 } 202 } 203 204 205 /* 206 ** create a new collectable object (with given type and size) and link 207 ** it to '*list'. 'offset' tells how many bytes to allocate before the 208 ** object itself (used only by states). 209 */ 210 GCObject *luaC_newobj (lua_State *L, int tt, size_t sz, GCObject **list, 211 int offset) { 212 global_State *g = G(L); 213 char *raw = cast(char *, luaM_newobject(L, novariant(tt), sz)); 214 GCObject *o = obj2gco(raw + offset); 215 if (list == NULL) 216 list = &g->allgc; /* standard list for collectable objects */ 217 gch(o)->marked = luaC_white(g); 218 gch(o)->tt = tt; 219 gch(o)->next = *list; 220 *list = o; 221 return o; 222 } 223 224 /* }====================================================== */ 225 226 227 228 /* 229 ** {====================================================== 230 ** Mark functions 231 ** ======================================================= 232 */ 233 234 235 /* 236 ** mark an object. Userdata, strings, and closed upvalues are visited 237 ** and turned black here. Other objects are marked gray and added 238 ** to appropriate list to be visited (and turned black) later. (Open 239 ** upvalues are already linked in 'headuv' list.) 240 */ 241 static void reallymarkobject (global_State *g, GCObject *o) { 242 lu_mem size; 243 white2gray(o); 244 switch (gch(o)->tt) { 245 case LUA_TSHRSTR: 246 case LUA_TLNGSTR: { 247 size = sizestring(gco2ts(o)); 248 break; /* nothing else to mark; make it black */ 249 } 250 case LUA_TUSERDATA: { 251 Table *mt = gco2u(o)->metatable; 252 markobject(g, mt); 253 markobject(g, gco2u(o)->env); 254 size = sizeudata(gco2u(o)); 255 break; 256 } 257 case LUA_TUPVAL: { 258 UpVal *uv = gco2uv(o); 259 markvalue(g, uv->v); 260 if (uv->v != &uv->u.value) /* open? */ 261 return; /* open upvalues remain gray */ 262 size = sizeof(UpVal); 263 break; 264 } 265 case LUA_TLCL: { 266 gco2lcl(o)->gclist = g->gray; 267 g->gray = o; 268 return; 269 } 270 case LUA_TCCL: { 271 gco2ccl(o)->gclist = g->gray; 272 g->gray = o; 273 return; 274 } 275 case LUA_TTABLE: { 276 linktable(gco2t(o), &g->gray); 277 return; 278 } 279 case LUA_TTHREAD: { 280 gco2th(o)->gclist = g->gray; 281 g->gray = o; 282 return; 283 } 284 case LUA_TPROTO: { 285 gco2p(o)->gclist = g->gray; 286 g->gray = o; 287 return; 288 } 289 default: lua_assert(0); return; 290 } 291 gray2black(o); 292 g->GCmemtrav += size; 293 } 294 295 296 /* 297 ** mark metamethods for basic types 298 */ 299 static void markmt (global_State *g) { 300 int i; 301 for (i=0; i < LUA_NUMTAGS; i++) 302 markobject(g, g->mt[i]); 303 } 304 305 306 /* 307 ** mark all objects in list of being-finalized 308 */ 309 static void markbeingfnz (global_State *g) { 310 GCObject *o; 311 for (o = g->tobefnz; o != NULL; o = gch(o)->next) { 312 makewhite(g, o); 313 reallymarkobject(g, o); 314 } 315 } 316 317 318 /* 319 ** mark all values stored in marked open upvalues. (See comment in 320 ** 'lstate.h'.) 321 */ 322 static void remarkupvals (global_State *g) { 323 UpVal *uv; 324 for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) { 325 if (isgray(obj2gco(uv))) 326 markvalue(g, uv->v); 327 } 328 } 329 330 331 /* 332 ** mark root set and reset all gray lists, to start a new 333 ** incremental (or full) collection 334 */ 335 static void restartcollection (global_State *g) { 336 g->gray = g->grayagain = NULL; 337 g->weak = g->allweak = g->ephemeron = NULL; 338 markobject(g, g->mainthread); 339 markvalue(g, &g->l_registry); 340 markmt(g); 341 markbeingfnz(g); /* mark any finalizing object left from previous cycle */ 342 } 343 344 /* }====================================================== */ 345 346 347 /* 348 ** {====================================================== 349 ** Traverse functions 350 ** ======================================================= 351 */ 352 353 static void traverseweakvalue (global_State *g, Table *h) { 354 Node *n, *limit = gnodelast(h); 355 /* if there is array part, assume it may have white values (do not 356 traverse it just to check) */ 357 int hasclears = (h->sizearray > 0); 358 for (n = gnode(h, 0); n < limit; n++) { 359 checkdeadkey(n); 360 if (ttisnil(gval(n))) /* entry is empty? */ 361 removeentry(n); /* remove it */ 362 else { 363 lua_assert(!ttisnil(gkey(n))); 364 markvalue(g, gkey(n)); /* mark key */ 365 if (!hasclears && iscleared(g, gval(n))) /* is there a white value? */ 366 hasclears = 1; /* table will have to be cleared */ 367 } 368 } 369 if (hasclears) 370 linktable(h, &g->weak); /* has to be cleared later */ 371 else /* no white values */ 372 linktable(h, &g->grayagain); /* no need to clean */ 373 } 374 375 376 static int traverseephemeron (global_State *g, Table *h) { 377 int marked = 0; /* true if an object is marked in this traversal */ 378 int hasclears = 0; /* true if table has white keys */ 379 int prop = 0; /* true if table has entry "white-key -> white-value" */ 380 Node *n, *limit = gnodelast(h); 381 int i; 382 /* traverse array part (numeric keys are 'strong') */ 383 for (i = 0; i < h->sizearray; i++) { 384 if (valiswhite(&h->array[i])) { 385 marked = 1; 386 reallymarkobject(g, gcvalue(&h->array[i])); 387 } 388 } 389 /* traverse hash part */ 390 for (n = gnode(h, 0); n < limit; n++) { 391 checkdeadkey(n); 392 if (ttisnil(gval(n))) /* entry is empty? */ 393 removeentry(n); /* remove it */ 394 else if (iscleared(g, gkey(n))) { /* key is not marked (yet)? */ 395 hasclears = 1; /* table must be cleared */ 396 if (valiswhite(gval(n))) /* value not marked yet? */ 397 prop = 1; /* must propagate again */ 398 } 399 else if (valiswhite(gval(n))) { /* value not marked yet? */ 400 marked = 1; 401 reallymarkobject(g, gcvalue(gval(n))); /* mark it now */ 402 } 403 } 404 if (g->gcstate != GCSatomic || prop) 405 linktable(h, &g->ephemeron); /* have to propagate again */ 406 else if (hasclears) /* does table have white keys? */ 407 linktable(h, &g->allweak); /* may have to clean white keys */ 408 else /* no white keys */ 409 linktable(h, &g->grayagain); /* no need to clean */ 410 return marked; 411 } 412 413 414 static void traversestrongtable (global_State *g, Table *h) { 415 Node *n, *limit = gnodelast(h); 416 int i; 417 for (i = 0; i < h->sizearray; i++) /* traverse array part */ 418 markvalue(g, &h->array[i]); 419 for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ 420 checkdeadkey(n); 421 if (ttisnil(gval(n))) /* entry is empty? */ 422 removeentry(n); /* remove it */ 423 else { 424 lua_assert(!ttisnil(gkey(n))); 425 markvalue(g, gkey(n)); /* mark key */ 426 markvalue(g, gval(n)); /* mark value */ 427 } 428 } 429 } 430 431 432 static lu_mem traversetable (global_State *g, Table *h) { 433 const char *weakkey, *weakvalue; 434 const TValue *mode = gfasttm(g, h->metatable, TM_MODE); 435 markobject(g, h->metatable); 436 if (mode && ttisstring(mode) && /* is there a weak mode? */ 437 ((weakkey = strchr(svalue(mode), 'k')), 438 (weakvalue = strchr(svalue(mode), 'v')), 439 (weakkey || weakvalue))) { /* is really weak? */ 440 black2gray(obj2gco(h)); /* keep table gray */ 441 if (!weakkey) /* strong keys? */ 442 traverseweakvalue(g, h); 443 else if (!weakvalue) /* strong values? */ 444 traverseephemeron(g, h); 445 else /* all weak */ 446 linktable(h, &g->allweak); /* nothing to traverse now */ 447 } 448 else /* not weak */ 449 traversestrongtable(g, h); 450 return sizeof(Table) + sizeof(TValue) * h->sizearray + 451 sizeof(Node) * cast(size_t, sizenode(h)); 452 } 453 454 455 static int traverseproto (global_State *g, Proto *f) { 456 int i; 457 if (f->cache && iswhite(obj2gco(f->cache))) 458 f->cache = NULL; /* allow cache to be collected */ 459 markobject(g, f->source); 460 for (i = 0; i < f->sizek; i++) /* mark literals */ 461 markvalue(g, &f->k[i]); 462 for (i = 0; i < f->sizeupvalues; i++) /* mark upvalue names */ 463 markobject(g, f->upvalues[i].name); 464 for (i = 0; i < f->sizep; i++) /* mark nested protos */ 465 markobject(g, f->p[i]); 466 for (i = 0; i < f->sizelocvars; i++) /* mark local-variable names */ 467 markobject(g, f->locvars[i].varname); 468 return sizeof(Proto) + sizeof(Instruction) * f->sizecode + 469 sizeof(Proto *) * f->sizep + 470 sizeof(TValue) * f->sizek + 471 sizeof(int) * f->sizelineinfo + 472 sizeof(LocVar) * f->sizelocvars + 473 sizeof(Upvaldesc) * f->sizeupvalues; 474 } 475 476 477 static lu_mem traverseCclosure (global_State *g, CClosure *cl) { 478 int i; 479 for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */ 480 markvalue(g, &cl->upvalue[i]); 481 return sizeCclosure(cl->nupvalues); 482 } 483 484 static lu_mem traverseLclosure (global_State *g, LClosure *cl) { 485 int i; 486 markobject(g, cl->p); /* mark its prototype */ 487 for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */ 488 markobject(g, cl->upvals[i]); 489 return sizeLclosure(cl->nupvalues); 490 } 491 492 493 static lu_mem traversestack (global_State *g, lua_State *th) { 494 int n = 0; 495 StkId o = th->stack; 496 if (o == NULL) 497 return 1; /* stack not completely built yet */ 498 for (; o < th->top; o++) /* mark live elements in the stack */ 499 markvalue(g, o); 500 if (g->gcstate == GCSatomic) { /* final traversal? */ 501 StkId lim = th->stack + th->stacksize; /* real end of stack */ 502 for (; o < lim; o++) /* clear not-marked stack slice */ 503 setnilvalue(o); 504 } 505 else { /* count call infos to compute size */ 506 CallInfo *ci; 507 for (ci = &th->base_ci; ci != th->ci; ci = ci->next) 508 n++; 509 } 510 return sizeof(lua_State) + sizeof(TValue) * th->stacksize + 511 sizeof(CallInfo) * n; 512 } 513 514 515 /* 516 ** traverse one gray object, turning it to black (except for threads, 517 ** which are always gray). 518 */ 519 static void propagatemark (global_State *g) { 520 lu_mem size; 521 GCObject *o = g->gray; 522 lua_assert(isgray(o)); 523 gray2black(o); 524 switch (gch(o)->tt) { 525 case LUA_TTABLE: { 526 Table *h = gco2t(o); 527 g->gray = h->gclist; /* remove from 'gray' list */ 528 size = traversetable(g, h); 529 break; 530 } 531 case LUA_TLCL: { 532 LClosure *cl = gco2lcl(o); 533 g->gray = cl->gclist; /* remove from 'gray' list */ 534 size = traverseLclosure(g, cl); 535 break; 536 } 537 case LUA_TCCL: { 538 CClosure *cl = gco2ccl(o); 539 g->gray = cl->gclist; /* remove from 'gray' list */ 540 size = traverseCclosure(g, cl); 541 break; 542 } 543 case LUA_TTHREAD: { 544 lua_State *th = gco2th(o); 545 g->gray = th->gclist; /* remove from 'gray' list */ 546 th->gclist = g->grayagain; 547 g->grayagain = o; /* insert into 'grayagain' list */ 548 black2gray(o); 549 size = traversestack(g, th); 550 break; 551 } 552 case LUA_TPROTO: { 553 Proto *p = gco2p(o); 554 g->gray = p->gclist; /* remove from 'gray' list */ 555 size = traverseproto(g, p); 556 break; 557 } 558 default: lua_assert(0); return; 559 } 560 g->GCmemtrav += size; 561 } 562 563 564 static void propagateall (global_State *g) { 565 while (g->gray) propagatemark(g); 566 } 567 568 569 static void propagatelist (global_State *g, GCObject *l) { 570 lua_assert(g->gray == NULL); /* no grays left */ 571 g->gray = l; 572 propagateall(g); /* traverse all elements from 'l' */ 573 } 574 575 /* 576 ** retraverse all gray lists. Because tables may be reinserted in other 577 ** lists when traversed, traverse the original lists to avoid traversing 578 ** twice the same table (which is not wrong, but inefficient) 579 */ 580 static void retraversegrays (global_State *g) { 581 GCObject *weak = g->weak; /* save original lists */ 582 GCObject *grayagain = g->grayagain; 583 GCObject *ephemeron = g->ephemeron; 584 g->weak = g->grayagain = g->ephemeron = NULL; 585 propagateall(g); /* traverse main gray list */ 586 propagatelist(g, grayagain); 587 propagatelist(g, weak); 588 propagatelist(g, ephemeron); 589 } 590 591 592 static void convergeephemerons (global_State *g) { 593 int changed; 594 do { 595 GCObject *w; 596 GCObject *next = g->ephemeron; /* get ephemeron list */ 597 g->ephemeron = NULL; /* tables will return to this list when traversed */ 598 changed = 0; 599 while ((w = next) != NULL) { 600 next = gco2t(w)->gclist; 601 if (traverseephemeron(g, gco2t(w))) { /* traverse marked some value? */ 602 propagateall(g); /* propagate changes */ 603 changed = 1; /* will have to revisit all ephemeron tables */ 604 } 605 } 606 } while (changed); 607 } 608 609 /* }====================================================== */ 610 611 612 /* 613 ** {====================================================== 614 ** Sweep Functions 615 ** ======================================================= 616 */ 617 618 619 /* 620 ** clear entries with unmarked keys from all weaktables in list 'l' up 621 ** to element 'f' 622 */ 623 static void clearkeys (global_State *g, GCObject *l, GCObject *f) { 624 for (; l != f; l = gco2t(l)->gclist) { 625 Table *h = gco2t(l); 626 Node *n, *limit = gnodelast(h); 627 for (n = gnode(h, 0); n < limit; n++) { 628 if (!ttisnil(gval(n)) && (iscleared(g, gkey(n)))) { 629 setnilvalue(gval(n)); /* remove value ... */ 630 removeentry(n); /* and remove entry from table */ 631 } 632 } 633 } 634 } 635 636 637 /* 638 ** clear entries with unmarked values from all weaktables in list 'l' up 639 ** to element 'f' 640 */ 641 static void clearvalues (global_State *g, GCObject *l, GCObject *f) { 642 for (; l != f; l = gco2t(l)->gclist) { 643 Table *h = gco2t(l); 644 Node *n, *limit = gnodelast(h); 645 int i; 646 for (i = 0; i < h->sizearray; i++) { 647 TValue *o = &h->array[i]; 648 if (iscleared(g, o)) /* value was collected? */ 649 setnilvalue(o); /* remove value */ 650 } 651 for (n = gnode(h, 0); n < limit; n++) { 652 if (!ttisnil(gval(n)) && iscleared(g, gval(n))) { 653 setnilvalue(gval(n)); /* remove value ... */ 654 removeentry(n); /* and remove entry from table */ 655 } 656 } 657 } 658 } 659 660 661 static void freeobj (lua_State *L, GCObject *o) { 662 switch (gch(o)->tt) { 663 case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break; 664 case LUA_TLCL: { 665 luaM_freemem(L, o, sizeLclosure(gco2lcl(o)->nupvalues)); 666 break; 667 } 668 case LUA_TCCL: { 669 luaM_freemem(L, o, sizeCclosure(gco2ccl(o)->nupvalues)); 670 break; 671 } 672 case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break; 673 case LUA_TTABLE: luaH_free(L, gco2t(o)); break; 674 case LUA_TTHREAD: luaE_freethread(L, gco2th(o)); break; 675 case LUA_TUSERDATA: luaM_freemem(L, o, sizeudata(gco2u(o))); break; 676 case LUA_TSHRSTR: 677 G(L)->strt.nuse--; 678 zfs_fallthrough; 679 case LUA_TLNGSTR: { 680 luaM_freemem(L, o, sizestring(gco2ts(o))); 681 break; 682 } 683 default: lua_assert(0); 684 } 685 } 686 687 688 #define sweepwholelist(L,p) sweeplist(L,p,MAX_LUMEM) 689 static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count); 690 691 692 /* 693 ** sweep the (open) upvalues of a thread and resize its stack and 694 ** list of call-info structures. 695 */ 696 static void sweepthread (lua_State *L, lua_State *L1) { 697 if (L1->stack == NULL) return; /* stack not completely built yet */ 698 sweepwholelist(L, &L1->openupval); /* sweep open upvalues */ 699 luaE_freeCI(L1); /* free extra CallInfo slots */ 700 /* should not change the stack during an emergency gc cycle */ 701 if (G(L)->gckind != KGC_EMERGENCY) 702 luaD_shrinkstack(L1); 703 } 704 705 706 /* 707 ** sweep at most 'count' elements from a list of GCObjects erasing dead 708 ** objects, where a dead (not alive) object is one marked with the "old" 709 ** (non current) white and not fixed. 710 ** In non-generational mode, change all non-dead objects back to white, 711 ** preparing for next collection cycle. 712 ** In generational mode, keep black objects black, and also mark them as 713 ** old; stop when hitting an old object, as all objects after that 714 ** one will be old too. 715 ** When object is a thread, sweep its list of open upvalues too. 716 */ 717 static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) { 718 global_State *g = G(L); 719 int ow = otherwhite(g); 720 int toclear, toset; /* bits to clear and to set in all live objects */ 721 int tostop; /* stop sweep when this is true */ 722 if (isgenerational(g)) { /* generational mode? */ 723 toclear = ~0; /* clear nothing */ 724 toset = bitmask(OLDBIT); /* set the old bit of all surviving objects */ 725 tostop = bitmask(OLDBIT); /* do not sweep old generation */ 726 } 727 else { /* normal mode */ 728 toclear = maskcolors; /* clear all color bits + old bit */ 729 toset = luaC_white(g); /* make object white */ 730 tostop = 0; /* do not stop */ 731 } 732 while (*p != NULL && count-- > 0) { 733 GCObject *curr = *p; 734 int marked = gch(curr)->marked; 735 if (isdeadm(ow, marked)) { /* is 'curr' dead? */ 736 *p = gch(curr)->next; /* remove 'curr' from list */ 737 freeobj(L, curr); /* erase 'curr' */ 738 } 739 else { 740 if (testbits(marked, tostop)) 741 return NULL; /* stop sweeping this list */ 742 if (gch(curr)->tt == LUA_TTHREAD) 743 sweepthread(L, gco2th(curr)); /* sweep thread's upvalues */ 744 /* update marks */ 745 gch(curr)->marked = cast_byte((marked & toclear) | toset); 746 p = &gch(curr)->next; /* go to next element */ 747 } 748 } 749 return (*p == NULL) ? NULL : p; 750 } 751 752 753 /* 754 ** sweep a list until a live object (or end of list) 755 */ 756 static GCObject **sweeptolive (lua_State *L, GCObject **p, int *n) { 757 GCObject ** old = p; 758 int i = 0; 759 do { 760 i++; 761 p = sweeplist(L, p, 1); 762 } while (p == old); 763 if (n) *n += i; 764 return p; 765 } 766 767 /* }====================================================== */ 768 769 770 /* 771 ** {====================================================== 772 ** Finalization 773 ** ======================================================= 774 */ 775 776 static void checkSizes (lua_State *L) { 777 global_State *g = G(L); 778 if (g->gckind != KGC_EMERGENCY) { /* do not change sizes in emergency */ 779 int hs = g->strt.size / 2; /* half the size of the string table */ 780 if (g->strt.nuse < cast(lu_int32, hs)) /* using less than that half? */ 781 luaS_resize(L, hs); /* halve its size */ 782 luaZ_freebuffer(L, &g->buff); /* free concatenation buffer */ 783 } 784 } 785 786 787 static GCObject *udata2finalize (global_State *g) { 788 GCObject *o = g->tobefnz; /* get first element */ 789 lua_assert(isfinalized(o)); 790 g->tobefnz = gch(o)->next; /* remove it from 'tobefnz' list */ 791 gch(o)->next = g->allgc; /* return it to 'allgc' list */ 792 g->allgc = o; 793 resetbit(gch(o)->marked, SEPARATED); /* mark that it is not in 'tobefnz' */ 794 lua_assert(!isold(o)); /* see MOVE OLD rule */ 795 if (!keepinvariantout(g)) /* not keeping invariant? */ 796 makewhite(g, o); /* "sweep" object */ 797 return o; 798 } 799 800 801 static void dothecall (lua_State *L, void *ud) { 802 UNUSED(ud); 803 luaD_call(L, L->top - 2, 0, 0); 804 } 805 806 807 static void GCTM (lua_State *L, int propagateerrors) { 808 global_State *g = G(L); 809 const TValue *tm; 810 TValue v; 811 setgcovalue(L, &v, udata2finalize(g)); 812 tm = luaT_gettmbyobj(L, &v, TM_GC); 813 if (tm != NULL && ttisfunction(tm)) { /* is there a finalizer? */ 814 int status; 815 lu_byte oldah = L->allowhook; 816 int running = g->gcrunning; 817 L->allowhook = 0; /* stop debug hooks during GC metamethod */ 818 g->gcrunning = 0; /* avoid GC steps */ 819 setobj2s(L, L->top, tm); /* push finalizer... */ 820 setobj2s(L, L->top + 1, &v); /* ... and its argument */ 821 L->top += 2; /* and (next line) call the finalizer */ 822 status = luaD_pcall(L, dothecall, NULL, savestack(L, L->top - 2), 0); 823 L->allowhook = oldah; /* restore hooks */ 824 g->gcrunning = running; /* restore state */ 825 if (status != LUA_OK && propagateerrors) { /* error while running __gc? */ 826 if (status == LUA_ERRRUN) { /* is there an error object? */ 827 const char *msg = (ttisstring(L->top - 1)) 828 ? svalue(L->top - 1) 829 : "no message"; 830 luaO_pushfstring(L, "error in __gc metamethod (%s)", msg); 831 status = LUA_ERRGCMM; /* error in __gc metamethod */ 832 } 833 luaD_throw(L, status); /* re-throw error */ 834 } 835 } 836 } 837 838 839 /* 840 ** move all unreachable objects (or 'all' objects) that need 841 ** finalization from list 'finobj' to list 'tobefnz' (to be finalized) 842 */ 843 static void separatetobefnz (lua_State *L, int all) { 844 global_State *g = G(L); 845 GCObject **p = &g->finobj; 846 GCObject *curr; 847 GCObject **lastnext = &g->tobefnz; 848 /* find last 'next' field in 'tobefnz' list (to add elements in its end) */ 849 while (*lastnext != NULL) 850 lastnext = &gch(*lastnext)->next; 851 while ((curr = *p) != NULL) { /* traverse all finalizable objects */ 852 lua_assert(!isfinalized(curr)); 853 lua_assert(testbit(gch(curr)->marked, SEPARATED)); 854 if (!(iswhite(curr) || all)) /* not being collected? */ 855 p = &gch(curr)->next; /* don't bother with it */ 856 else { 857 l_setbit(gch(curr)->marked, FINALIZEDBIT); /* won't be finalized again */ 858 *p = gch(curr)->next; /* remove 'curr' from 'finobj' list */ 859 gch(curr)->next = *lastnext; /* link at the end of 'tobefnz' list */ 860 *lastnext = curr; 861 lastnext = &gch(curr)->next; 862 } 863 } 864 } 865 866 867 /* 868 ** if object 'o' has a finalizer, remove it from 'allgc' list (must 869 ** search the list to find it) and link it in 'finobj' list. 870 */ 871 void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) { 872 global_State *g = G(L); 873 if (testbit(gch(o)->marked, SEPARATED) || /* obj. is already separated... */ 874 isfinalized(o) || /* ... or is finalized... */ 875 gfasttm(g, mt, TM_GC) == NULL) /* or has no finalizer? */ 876 return; /* nothing to be done */ 877 else { /* move 'o' to 'finobj' list */ 878 GCObject **p; 879 GCheader *ho = gch(o); 880 if (g->sweepgc == &ho->next) { /* avoid removing current sweep object */ 881 lua_assert(issweepphase(g)); 882 g->sweepgc = sweeptolive(L, g->sweepgc, NULL); 883 } 884 /* search for pointer pointing to 'o' */ 885 for (p = &g->allgc; *p != o; p = &gch(*p)->next) { /* empty */ } 886 *p = ho->next; /* remove 'o' from root list */ 887 ho->next = g->finobj; /* link it in list 'finobj' */ 888 g->finobj = o; 889 l_setbit(ho->marked, SEPARATED); /* mark it as such */ 890 if (!keepinvariantout(g)) /* not keeping invariant? */ 891 makewhite(g, o); /* "sweep" object */ 892 else 893 resetoldbit(o); /* see MOVE OLD rule */ 894 } 895 } 896 897 /* }====================================================== */ 898 899 900 /* 901 ** {====================================================== 902 ** GC control 903 ** ======================================================= 904 */ 905 906 907 /* 908 ** set a reasonable "time" to wait before starting a new GC cycle; 909 ** cycle will start when memory use hits threshold 910 */ 911 static void setpause (global_State *g, l_mem estimate) { 912 l_mem debt, threshold; 913 estimate = estimate / PAUSEADJ; /* adjust 'estimate' */ 914 threshold = (g->gcpause < MAX_LMEM / estimate) /* overflow? */ 915 ? estimate * g->gcpause /* no overflow */ 916 : MAX_LMEM; /* overflow; truncate to maximum */ 917 debt = -cast(l_mem, threshold - gettotalbytes(g)); 918 luaE_setdebt(g, debt); 919 } 920 921 922 #define sweepphases \ 923 (bitmask(GCSsweepstring) | bitmask(GCSsweepudata) | bitmask(GCSsweep)) 924 925 926 /* 927 ** enter first sweep phase (strings) and prepare pointers for other 928 ** sweep phases. The calls to 'sweeptolive' make pointers point to an 929 ** object inside the list (instead of to the header), so that the real 930 ** sweep do not need to skip objects created between "now" and the start 931 ** of the real sweep. 932 ** Returns how many objects it swept. 933 */ 934 static int entersweep (lua_State *L) { 935 global_State *g = G(L); 936 int n = 0; 937 g->gcstate = GCSsweepstring; 938 lua_assert(g->sweepgc == NULL && g->sweepfin == NULL); 939 /* prepare to sweep strings, finalizable objects, and regular objects */ 940 g->sweepstrgc = 0; 941 g->sweepfin = sweeptolive(L, &g->finobj, &n); 942 g->sweepgc = sweeptolive(L, &g->allgc, &n); 943 return n; 944 } 945 946 947 /* 948 ** change GC mode 949 */ 950 void luaC_changemode (lua_State *L, int mode) { 951 global_State *g = G(L); 952 if (mode == g->gckind) return; /* nothing to change */ 953 if (mode == KGC_GEN) { /* change to generational mode */ 954 /* make sure gray lists are consistent */ 955 luaC_runtilstate(L, bitmask(GCSpropagate)); 956 g->GCestimate = gettotalbytes(g); 957 g->gckind = KGC_GEN; 958 } 959 else { /* change to incremental mode */ 960 /* sweep all objects to turn them back to white 961 (as white has not changed, nothing extra will be collected) */ 962 g->gckind = KGC_NORMAL; 963 entersweep(L); 964 luaC_runtilstate(L, ~sweepphases); 965 } 966 } 967 968 969 /* 970 ** call all pending finalizers 971 */ 972 static void callallpendingfinalizers (lua_State *L, int propagateerrors) { 973 global_State *g = G(L); 974 while (g->tobefnz) { 975 resetoldbit(g->tobefnz); 976 GCTM(L, propagateerrors); 977 } 978 } 979 980 981 void luaC_freeallobjects (lua_State *L) { 982 global_State *g = G(L); 983 int i; 984 separatetobefnz(L, 1); /* separate all objects with finalizers */ 985 lua_assert(g->finobj == NULL); 986 callallpendingfinalizers(L, 0); 987 g->currentwhite = WHITEBITS; /* this "white" makes all objects look dead */ 988 g->gckind = KGC_NORMAL; 989 sweepwholelist(L, &g->finobj); /* finalizers can create objs. in 'finobj' */ 990 sweepwholelist(L, &g->allgc); 991 for (i = 0; i < g->strt.size; i++) /* free all string lists */ 992 sweepwholelist(L, &g->strt.hash[i]); 993 lua_assert(g->strt.nuse == 0); 994 } 995 996 997 static l_mem atomic (lua_State *L) { 998 global_State *g = G(L); 999 l_mem work = -cast(l_mem, g->GCmemtrav); /* start counting work */ 1000 GCObject *origweak, *origall; 1001 lua_assert(!iswhite(obj2gco(g->mainthread))); 1002 markobject(g, L); /* mark running thread */ 1003 /* registry and global metatables may be changed by API */ 1004 markvalue(g, &g->l_registry); 1005 markmt(g); /* mark basic metatables */ 1006 /* remark occasional upvalues of (maybe) dead threads */ 1007 remarkupvals(g); 1008 propagateall(g); /* propagate changes */ 1009 work += g->GCmemtrav; /* stop counting (do not (re)count grays) */ 1010 /* traverse objects caught by write barrier and by 'remarkupvals' */ 1011 retraversegrays(g); 1012 work -= g->GCmemtrav; /* restart counting */ 1013 convergeephemerons(g); 1014 /* at this point, all strongly accessible objects are marked. */ 1015 /* clear values from weak tables, before checking finalizers */ 1016 clearvalues(g, g->weak, NULL); 1017 clearvalues(g, g->allweak, NULL); 1018 origweak = g->weak; origall = g->allweak; 1019 work += g->GCmemtrav; /* stop counting (objects being finalized) */ 1020 separatetobefnz(L, 0); /* separate objects to be finalized */ 1021 markbeingfnz(g); /* mark objects that will be finalized */ 1022 propagateall(g); /* remark, to propagate `preserveness' */ 1023 work -= g->GCmemtrav; /* restart counting */ 1024 convergeephemerons(g); 1025 /* at this point, all resurrected objects are marked. */ 1026 /* remove dead objects from weak tables */ 1027 clearkeys(g, g->ephemeron, NULL); /* clear keys from all ephemeron tables */ 1028 clearkeys(g, g->allweak, NULL); /* clear keys from all allweak tables */ 1029 /* clear values from resurrected weak tables */ 1030 clearvalues(g, g->weak, origweak); 1031 clearvalues(g, g->allweak, origall); 1032 g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */ 1033 work += g->GCmemtrav; /* complete counting */ 1034 return work; /* estimate of memory marked by 'atomic' */ 1035 } 1036 1037 1038 static lu_mem singlestep (lua_State *L) { 1039 global_State *g = G(L); 1040 switch (g->gcstate) { 1041 case GCSpause: { 1042 /* start to count memory traversed */ 1043 g->GCmemtrav = g->strt.size * sizeof(GCObject*); 1044 lua_assert(!isgenerational(g)); 1045 restartcollection(g); 1046 g->gcstate = GCSpropagate; 1047 return g->GCmemtrav; 1048 } 1049 case GCSpropagate: { 1050 if (g->gray) { 1051 lu_mem oldtrav = g->GCmemtrav; 1052 propagatemark(g); 1053 return g->GCmemtrav - oldtrav; /* memory traversed in this step */ 1054 } 1055 else { /* no more `gray' objects */ 1056 lu_mem work; 1057 int sw; 1058 g->gcstate = GCSatomic; /* finish mark phase */ 1059 g->GCestimate = g->GCmemtrav; /* save what was counted */; 1060 work = atomic(L); /* add what was traversed by 'atomic' */ 1061 g->GCestimate += work; /* estimate of total memory traversed */ 1062 sw = entersweep(L); 1063 return work + sw * GCSWEEPCOST; 1064 } 1065 } 1066 case GCSsweepstring: { 1067 int i; 1068 for (i = 0; i < GCSWEEPMAX && g->sweepstrgc + i < g->strt.size; i++) 1069 sweepwholelist(L, &g->strt.hash[g->sweepstrgc + i]); 1070 g->sweepstrgc += i; 1071 if (g->sweepstrgc >= g->strt.size) /* no more strings to sweep? */ 1072 g->gcstate = GCSsweepudata; 1073 return i * GCSWEEPCOST; 1074 } 1075 case GCSsweepudata: { 1076 if (g->sweepfin) { 1077 g->sweepfin = sweeplist(L, g->sweepfin, GCSWEEPMAX); 1078 return GCSWEEPMAX*GCSWEEPCOST; 1079 } 1080 else { 1081 g->gcstate = GCSsweep; 1082 return 0; 1083 } 1084 } 1085 case GCSsweep: { 1086 if (g->sweepgc) { 1087 g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX); 1088 return GCSWEEPMAX*GCSWEEPCOST; 1089 } 1090 else { 1091 /* sweep main thread */ 1092 GCObject *mt = obj2gco(g->mainthread); 1093 sweeplist(L, &mt, 1); 1094 checkSizes(L); 1095 g->gcstate = GCSpause; /* finish collection */ 1096 return GCSWEEPCOST; 1097 } 1098 } 1099 default: lua_assert(0); return 0; 1100 } 1101 } 1102 1103 1104 /* 1105 ** advances the garbage collector until it reaches a state allowed 1106 ** by 'statemask' 1107 */ 1108 void luaC_runtilstate (lua_State *L, int statesmask) { 1109 global_State *g = G(L); 1110 while (!testbit(statesmask, g->gcstate)) 1111 singlestep(L); 1112 } 1113 1114 1115 static void generationalcollection (lua_State *L) { 1116 global_State *g = G(L); 1117 lua_assert(g->gcstate == GCSpropagate); 1118 if (g->GCestimate == 0) { /* signal for another major collection? */ 1119 luaC_fullgc(L, 0); /* perform a full regular collection */ 1120 g->GCestimate = gettotalbytes(g); /* update control */ 1121 } 1122 else { 1123 lu_mem estimate = g->GCestimate; 1124 luaC_runtilstate(L, bitmask(GCSpause)); /* run complete (minor) cycle */ 1125 g->gcstate = GCSpropagate; /* skip restart */ 1126 if (gettotalbytes(g) > (estimate / 100) * g->gcmajorinc) 1127 g->GCestimate = 0; /* signal for a major collection */ 1128 else 1129 g->GCestimate = estimate; /* keep estimate from last major coll. */ 1130 1131 } 1132 setpause(g, gettotalbytes(g)); 1133 lua_assert(g->gcstate == GCSpropagate); 1134 } 1135 1136 1137 static void incstep (lua_State *L) { 1138 global_State *g = G(L); 1139 l_mem debt = g->GCdebt; 1140 int stepmul = g->gcstepmul; 1141 if (stepmul < 40) stepmul = 40; /* avoid ridiculous low values (and 0) */ 1142 /* convert debt from Kb to 'work units' (avoid zero debt and overflows) */ 1143 debt = (debt / STEPMULADJ) + 1; 1144 debt = (debt < MAX_LMEM / stepmul) ? debt * stepmul : MAX_LMEM; 1145 do { /* always perform at least one single step */ 1146 lu_mem work = singlestep(L); /* do some work */ 1147 debt -= work; 1148 } while (debt > -GCSTEPSIZE && g->gcstate != GCSpause); 1149 if (g->gcstate == GCSpause) 1150 setpause(g, g->GCestimate); /* pause until next cycle */ 1151 else { 1152 debt = (debt / stepmul) * STEPMULADJ; /* convert 'work units' to Kb */ 1153 luaE_setdebt(g, debt); 1154 } 1155 } 1156 1157 1158 /* 1159 ** performs a basic GC step 1160 */ 1161 void luaC_forcestep (lua_State *L) { 1162 global_State *g = G(L); 1163 int i; 1164 if (isgenerational(g)) generationalcollection(L); 1165 else incstep(L); 1166 /* run a few finalizers (or all of them at the end of a collect cycle) */ 1167 for (i = 0; g->tobefnz && (i < GCFINALIZENUM || g->gcstate == GCSpause); i++) 1168 GCTM(L, 1); /* call one finalizer */ 1169 } 1170 1171 1172 /* 1173 ** performs a basic GC step only if collector is running 1174 */ 1175 void luaC_step (lua_State *L) { 1176 global_State *g = G(L); 1177 if (g->gcrunning) luaC_forcestep(L); 1178 else luaE_setdebt(g, -GCSTEPSIZE); /* avoid being called too often */ 1179 } 1180 1181 1182 1183 /* 1184 ** performs a full GC cycle; if "isemergency", does not call 1185 ** finalizers (which could change stack positions) 1186 */ 1187 void luaC_fullgc (lua_State *L, int isemergency) { 1188 global_State *g = G(L); 1189 int origkind = g->gckind; 1190 lua_assert(origkind != KGC_EMERGENCY); 1191 if (isemergency) /* do not run finalizers during emergency GC */ 1192 g->gckind = KGC_EMERGENCY; 1193 else { 1194 g->gckind = KGC_NORMAL; 1195 callallpendingfinalizers(L, 1); 1196 } 1197 if (keepinvariant(g)) { /* may there be some black objects? */ 1198 /* must sweep all objects to turn them back to white 1199 (as white has not changed, nothing will be collected) */ 1200 entersweep(L); 1201 } 1202 /* finish any pending sweep phase to start a new cycle */ 1203 luaC_runtilstate(L, bitmask(GCSpause)); 1204 luaC_runtilstate(L, ~bitmask(GCSpause)); /* start new collection */ 1205 luaC_runtilstate(L, bitmask(GCSpause)); /* run entire collection */ 1206 if (origkind == KGC_GEN) { /* generational mode? */ 1207 /* generational mode must be kept in propagate phase */ 1208 luaC_runtilstate(L, bitmask(GCSpropagate)); 1209 } 1210 g->gckind = origkind; 1211 setpause(g, gettotalbytes(g)); 1212 if (!isemergency) /* do not run finalizers during emergency GC */ 1213 callallpendingfinalizers(L, 1); 1214 } 1215 1216 /* }====================================================== */ 1217