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