aboutsummaryrefslogtreecommitdiff
path: root/lgc.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lgc.c416
1 files changed, 175 insertions, 241 deletions
diff --git a/lgc.c b/lgc.c
index f291cd17..e4f8e396 100644
--- a/lgc.c
+++ b/lgc.c
@@ -9,7 +9,6 @@
9 9
10#include "lprefix.h" 10#include "lprefix.h"
11 11
12#include <stdio.h>
13#include <string.h> 12#include <string.h>
14 13
15 14
@@ -19,6 +18,7 @@
19#include "ldo.h" 18#include "ldo.h"
20#include "lfunc.h" 19#include "lfunc.h"
21#include "lgc.h" 20#include "lgc.h"
21#include "llex.h"
22#include "lmem.h" 22#include "lmem.h"
23#include "lobject.h" 23#include "lobject.h"
24#include "lstate.h" 24#include "lstate.h"
@@ -28,36 +28,18 @@
28 28
29 29
30/* 30/*
31** Maximum number of elements to sweep in each single step. 31** Number of fixed (luaC_fix) objects in a Lua state: metafield names,
32** (Large enough to dissipate fixed overheads but small enough 32** plus reserved words, plus "_ENV", plus the memory-error message.
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*/ 33*/
53#define WORK2MEM sizeof(TValue) 34#define NFIXED (TM_N + NUM_RESERVED + 2)
54 35
55 36
56/* 37/*
57** macro to adjust 'pause': 'pause' is actually used like 38** Maximum number of elements to sweep in each single step.
58** 'pause / PAUSEADJ' (value chosen by tests) 39** (Large enough to dissipate fixed overheads but small enough
40** to allow small steps for the collector.)
59*/ 41*/
60#define PAUSEADJ 100 42#define GCSWEEPMAX 20
61 43
62 44
63/* mask with all color bits */ 45/* mask with all color bits */
@@ -112,7 +94,7 @@
112#define markobjectN(g,t) { if (t) markobject(g,t); } 94#define markobjectN(g,t) { if (t) markobject(g,t); }
113 95
114static void reallymarkobject (global_State *g, GCObject *o); 96static void reallymarkobject (global_State *g, GCObject *o);
115static lu_mem atomic (lua_State *L); 97static l_obj atomic (lua_State *L);
116static void entersweep (lua_State *L); 98static void entersweep (lua_State *L);
117 99
118 100
@@ -224,7 +206,7 @@ void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
224 } 206 }
225 else { /* sweep phase */ 207 else { /* sweep phase */
226 lua_assert(issweepphase(g)); 208 lua_assert(issweepphase(g));
227 if (g->gckind == KGC_INC) /* incremental mode? */ 209 if (g->gckind != KGC_GEN) /* incremental mode? */
228 makewhite(g, o); /* mark 'o' as white to avoid other barriers */ 210 makewhite(g, o); /* mark 'o' as white to avoid other barriers */
229 } 211 }
230} 212}
@@ -266,6 +248,7 @@ GCObject *luaC_newobjdt (lua_State *L, int tt, size_t sz, size_t offset) {
266 global_State *g = G(L); 248 global_State *g = G(L);
267 char *p = cast_charp(luaM_newobject(L, novariant(tt), sz)); 249 char *p = cast_charp(luaM_newobject(L, novariant(tt), sz));
268 GCObject *o = cast(GCObject *, p + offset); 250 GCObject *o = cast(GCObject *, p + offset);
251 g->GCdebt--;
269 o->marked = luaC_white(g); 252 o->marked = luaC_white(g);
270 o->tt = tt; 253 o->tt = tt;
271 o->next = g->allgc; 254 o->next = g->allgc;
@@ -274,6 +257,9 @@ GCObject *luaC_newobjdt (lua_State *L, int tt, size_t sz, size_t offset) {
274} 257}
275 258
276 259
260/*
261** create a new collectable object with no offset.
262*/
277GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) { 263GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
278 return luaC_newobjdt(L, tt, sz, 0); 264 return luaC_newobjdt(L, tt, sz, 0);
279} 265}
@@ -302,6 +288,7 @@ GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
302** (only closures can), and a userdata's metatable must be a table. 288** (only closures can), and a userdata's metatable must be a table.
303*/ 289*/
304static void reallymarkobject (global_State *g, GCObject *o) { 290static void reallymarkobject (global_State *g, GCObject *o) {
291 g->marked++;
305 switch (o->tt) { 292 switch (o->tt) {
306 case LUA_VSHRSTR: 293 case LUA_VSHRSTR:
307 case LUA_VLNGSTR: { 294 case LUA_VLNGSTR: {
@@ -349,9 +336,9 @@ static void markmt (global_State *g) {
349/* 336/*
350** mark all objects in list of being-finalized 337** mark all objects in list of being-finalized
351*/ 338*/
352static lu_mem markbeingfnz (global_State *g) { 339static l_obj markbeingfnz (global_State *g) {
353 GCObject *o; 340 GCObject *o;
354 lu_mem count = 0; 341 l_obj count = 0;
355 for (o = g->tobefnz; o != NULL; o = o->next) { 342 for (o = g->tobefnz; o != NULL; o = o->next) {
356 count++; 343 count++;
357 markobject(g, o); 344 markobject(g, o);
@@ -371,12 +358,11 @@ static lu_mem markbeingfnz (global_State *g) {
371** upvalues, as they have nothing to be checked. (If the thread gets an 358** upvalues, as they have nothing to be checked. (If the thread gets an
372** upvalue later, it will be linked in the list again.) 359** upvalue later, it will be linked in the list again.)
373*/ 360*/
374static int remarkupvals (global_State *g) { 361static l_obj remarkupvals (global_State *g) {
362 l_obj work = 0;
375 lua_State *thread; 363 lua_State *thread;
376 lua_State **p = &g->twups; 364 lua_State **p = &g->twups;
377 int work = 0; /* estimate of how much work was done here */
378 while ((thread = *p) != NULL) { 365 while ((thread = *p) != NULL) {
379 work++;
380 if (!iswhite(thread) && thread->openupval != NULL) 366 if (!iswhite(thread) && thread->openupval != NULL)
381 p = &thread->twups; /* keep marked thread with upvalues in the list */ 367 p = &thread->twups; /* keep marked thread with upvalues in the list */
382 else { /* thread is not marked or without upvalues */ 368 else { /* thread is not marked or without upvalues */
@@ -386,13 +372,13 @@ static int remarkupvals (global_State *g) {
386 thread->twups = thread; /* mark that it is out of list */ 372 thread->twups = thread; /* mark that it is out of list */
387 for (uv = thread->openupval; uv != NULL; uv = uv->u.open.next) { 373 for (uv = thread->openupval; uv != NULL; uv = uv->u.open.next) {
388 lua_assert(getage(uv) <= getage(thread)); 374 lua_assert(getage(uv) <= getage(thread));
389 work++;
390 if (!iswhite(uv)) { /* upvalue already visited? */ 375 if (!iswhite(uv)) { /* upvalue already visited? */
391 lua_assert(upisopen(uv) && isgray(uv)); 376 lua_assert(upisopen(uv) && isgray(uv));
392 markvalue(g, uv->v.p); /* mark its value */ 377 markvalue(g, uv->v.p); /* mark its value */
393 } 378 }
394 } 379 }
395 } 380 }
381 work++;
396 } 382 }
397 return work; 383 return work;
398} 384}
@@ -405,10 +391,15 @@ static void cleargraylists (global_State *g) {
405 391
406 392
407/* 393/*
408** mark root set and reset all gray lists, to start a new collection 394** mark root set and reset all gray lists, to start a new collection.
395** 'marked' is initialized with the number of fixed objects in the state,
396** to count the total number of live objects during a cycle. (That is
397** the metafield names, plus the reserved words, plus "_ENV" plus the
398** memory-error message.)
409*/ 399*/
410static void restartcollection (global_State *g) { 400static void restartcollection (global_State *g) {
411 cleargraylists(g); 401 cleargraylists(g);
402 g->marked = NFIXED;
412 markobject(g, g->mainthread); 403 markobject(g, g->mainthread);
413 markvalue(g, &g->l_registry); 404 markvalue(g, &g->l_registry);
414 markmt(g); 405 markmt(g);
@@ -550,7 +541,7 @@ static void traversestrongtable (global_State *g, Table *h) {
550} 541}
551 542
552 543
553static lu_mem traversetable (global_State *g, Table *h) { 544static void traversetable (global_State *g, Table *h) {
554 const char *weakkey, *weakvalue; 545 const char *weakkey, *weakvalue;
555 const TValue *mode = gfasttm(g, h->metatable, TM_MODE); 546 const TValue *mode = gfasttm(g, h->metatable, TM_MODE);
556 TString *smode; 547 TString *smode;
@@ -569,17 +560,15 @@ static lu_mem traversetable (global_State *g, Table *h) {
569 } 560 }
570 else /* not weak */ 561 else /* not weak */
571 traversestrongtable(g, h); 562 traversestrongtable(g, h);
572 return 1 + h->alimit + 2 * allocsizenode(h);
573} 563}
574 564
575 565
576static int traverseudata (global_State *g, Udata *u) { 566static void traverseudata (global_State *g, Udata *u) {
577 int i; 567 int i;
578 markobjectN(g, u->metatable); /* mark its metatable */ 568 markobjectN(g, u->metatable); /* mark its metatable */
579 for (i = 0; i < u->nuvalue; i++) 569 for (i = 0; i < u->nuvalue; i++)
580 markvalue(g, &u->uv[i].uv); 570 markvalue(g, &u->uv[i].uv);
581 genlink(g, obj2gco(u)); 571 genlink(g, obj2gco(u));
582 return 1 + u->nuvalue;
583} 572}
584 573
585 574
@@ -588,7 +577,7 @@ static int traverseudata (global_State *g, Udata *u) {
588** arrays can be larger than needed; the extra slots are filled with 577** arrays can be larger than needed; the extra slots are filled with
589** NULL, so the use of 'markobjectN') 578** NULL, so the use of 'markobjectN')
590*/ 579*/
591static int traverseproto (global_State *g, Proto *f) { 580static void traverseproto (global_State *g, Proto *f) {
592 int i; 581 int i;
593 markobjectN(g, f->source); 582 markobjectN(g, f->source);
594 for (i = 0; i < f->sizek; i++) /* mark literals */ 583 for (i = 0; i < f->sizek; i++) /* mark literals */
@@ -599,29 +588,26 @@ static int traverseproto (global_State *g, Proto *f) {
599 markobjectN(g, f->p[i]); 588 markobjectN(g, f->p[i]);
600 for (i = 0; i < f->sizelocvars; i++) /* mark local-variable names */ 589 for (i = 0; i < f->sizelocvars; i++) /* mark local-variable names */
601 markobjectN(g, f->locvars[i].varname); 590 markobjectN(g, f->locvars[i].varname);
602 return 1 + f->sizek + f->sizeupvalues + f->sizep + f->sizelocvars;
603} 591}
604 592
605 593
606static int traverseCclosure (global_State *g, CClosure *cl) { 594static void traverseCclosure (global_State *g, CClosure *cl) {
607 int i; 595 int i;
608 for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */ 596 for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */
609 markvalue(g, &cl->upvalue[i]); 597 markvalue(g, &cl->upvalue[i]);
610 return 1 + cl->nupvalues;
611} 598}
612 599
613/* 600/*
614** Traverse a Lua closure, marking its prototype and its upvalues. 601** Traverse a Lua closure, marking its prototype and its upvalues.
615** (Both can be NULL while closure is being created.) 602** (Both can be NULL while closure is being created.)
616*/ 603*/
617static int traverseLclosure (global_State *g, LClosure *cl) { 604static void traverseLclosure (global_State *g, LClosure *cl) {
618 int i; 605 int i;
619 markobjectN(g, cl->p); /* mark its prototype */ 606 markobjectN(g, cl->p); /* mark its prototype */
620 for (i = 0; i < cl->nupvalues; i++) { /* visit its upvalues */ 607 for (i = 0; i < cl->nupvalues; i++) { /* visit its upvalues */
621 UpVal *uv = cl->upvals[i]; 608 UpVal *uv = cl->upvals[i];
622 markobjectN(g, uv); /* mark upvalue */ 609 markobjectN(g, uv); /* mark upvalue */
623 } 610 }
624 return 1 + cl->nupvalues;
625} 611}
626 612
627 613
@@ -637,13 +623,13 @@ static int traverseLclosure (global_State *g, LClosure *cl) {
637** (which can only happen in generational mode) or if the traverse is in 623** (which can only happen in generational mode) or if the traverse is in
638** the propagate phase (which can only happen in incremental mode). 624** the propagate phase (which can only happen in incremental mode).
639*/ 625*/
640static int traversethread (global_State *g, lua_State *th) { 626static void traversethread (global_State *g, lua_State *th) {
641 UpVal *uv; 627 UpVal *uv;
642 StkId o = th->stack.p; 628 StkId o = th->stack.p;
643 if (isold(th) || g->gcstate == GCSpropagate) 629 if (isold(th) || g->gcstate == GCSpropagate)
644 linkgclist(th, g->grayagain); /* insert into 'grayagain' list */ 630 linkgclist(th, g->grayagain); /* insert into 'grayagain' list */
645 if (o == NULL) 631 if (o == NULL)
646 return 1; /* stack not completely built yet */ 632 return; /* stack not completely built yet */
647 lua_assert(g->gcstate == GCSatomic || 633 lua_assert(g->gcstate == GCSatomic ||
648 th->openupval == NULL || isintwups(th)); 634 th->openupval == NULL || isintwups(th));
649 for (; o < th->top.p; o++) /* mark live elements in the stack */ 635 for (; o < th->top.p; o++) /* mark live elements in the stack */
@@ -661,34 +647,35 @@ static int traversethread (global_State *g, lua_State *th) {
661 g->twups = th; 647 g->twups = th;
662 } 648 }
663 } 649 }
664 return 1 + stacksize(th);
665} 650}
666 651
667 652
668/* 653/*
669** traverse one gray object, turning it to black. 654** traverse one gray object, turning it to black.
670*/ 655*/
671static lu_mem propagatemark (global_State *g) { 656static void propagatemark (global_State *g) {
672 GCObject *o = g->gray; 657 GCObject *o = g->gray;
673 nw2black(o); 658 nw2black(o);
674 g->gray = *getgclist(o); /* remove from 'gray' list */ 659 g->gray = *getgclist(o); /* remove from 'gray' list */
675 switch (o->tt) { 660 switch (o->tt) {
676 case LUA_VTABLE: return traversetable(g, gco2t(o)); 661 case LUA_VTABLE: traversetable(g, gco2t(o)); break;
677 case LUA_VUSERDATA: return traverseudata(g, gco2u(o)); 662 case LUA_VUSERDATA: traverseudata(g, gco2u(o)); break;
678 case LUA_VLCL: return traverseLclosure(g, gco2lcl(o)); 663 case LUA_VLCL: traverseLclosure(g, gco2lcl(o)); break;
679 case LUA_VCCL: return traverseCclosure(g, gco2ccl(o)); 664 case LUA_VCCL: traverseCclosure(g, gco2ccl(o)); break;
680 case LUA_VPROTO: return traverseproto(g, gco2p(o)); 665 case LUA_VPROTO: traverseproto(g, gco2p(o)); break;
681 case LUA_VTHREAD: return traversethread(g, gco2th(o)); 666 case LUA_VTHREAD: traversethread(g, gco2th(o)); break;
682 default: lua_assert(0); return 0; 667 default: lua_assert(0);
683 } 668 }
684} 669}
685 670
686 671
687static lu_mem propagateall (global_State *g) { 672static l_obj propagateall (global_State *g) {
688 lu_mem tot = 0; 673 l_obj work = 0;
689 while (g->gray) 674 while (g->gray) {
690 tot += propagatemark(g); 675 propagatemark(g);
691 return tot; 676 work++;
677 }
678 return work;
692} 679}
693 680
694 681
@@ -697,10 +684,10 @@ static lu_mem propagateall (global_State *g) {
697** Repeat until it converges, that is, nothing new is marked. 'dir' 684** Repeat until it converges, that is, nothing new is marked. 'dir'
698** inverts the direction of the traversals, trying to speed up 685** inverts the direction of the traversals, trying to speed up
699** convergence on chains in the same table. 686** convergence on chains in the same table.
700**
701*/ 687*/
702static void convergeephemerons (global_State *g) { 688static l_obj convergeephemerons (global_State *g) {
703 int changed; 689 int changed;
690 l_obj work = 0;
704 int dir = 0; 691 int dir = 0;
705 do { 692 do {
706 GCObject *w; 693 GCObject *w;
@@ -715,9 +702,11 @@ static void convergeephemerons (global_State *g) {
715 propagateall(g); /* propagate changes */ 702 propagateall(g); /* propagate changes */
716 changed = 1; /* will have to revisit all ephemeron tables */ 703 changed = 1; /* will have to revisit all ephemeron tables */
717 } 704 }
705 work++;
718 } 706 }
719 dir = !dir; /* invert direction next time */ 707 dir = !dir; /* invert direction next time */
720 } while (changed); /* repeat until no more changes */ 708 } while (changed); /* repeat until no more changes */
709 return work;
721} 710}
722 711
723/* }====================================================== */ 712/* }====================================================== */
@@ -733,7 +722,8 @@ static void convergeephemerons (global_State *g) {
733/* 722/*
734** clear entries with unmarked keys from all weaktables in list 'l' 723** clear entries with unmarked keys from all weaktables in list 'l'
735*/ 724*/
736static void clearbykeys (global_State *g, GCObject *l) { 725static l_obj clearbykeys (global_State *g, GCObject *l) {
726 l_obj work = 0;
737 for (; l; l = gco2t(l)->gclist) { 727 for (; l; l = gco2t(l)->gclist) {
738 Table *h = gco2t(l); 728 Table *h = gco2t(l);
739 Node *limit = gnodelast(h); 729 Node *limit = gnodelast(h);
@@ -744,7 +734,9 @@ static void clearbykeys (global_State *g, GCObject *l) {
744 if (isempty(gval(n))) /* is entry empty? */ 734 if (isempty(gval(n))) /* is entry empty? */
745 clearkey(n); /* clear its key */ 735 clearkey(n); /* clear its key */
746 } 736 }
737 work++;
747 } 738 }
739 return work;
748} 740}
749 741
750 742
@@ -752,7 +744,8 @@ static void clearbykeys (global_State *g, GCObject *l) {
752** clear entries with unmarked values from all weaktables in list 'l' up 744** clear entries with unmarked values from all weaktables in list 'l' up
753** to element 'f' 745** to element 'f'
754*/ 746*/
755static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) { 747static l_obj clearbyvalues (global_State *g, GCObject *l, GCObject *f) {
748 l_obj work = 0;
756 for (; l != f; l = gco2t(l)->gclist) { 749 for (; l != f; l = gco2t(l)->gclist) {
757 Table *h = gco2t(l); 750 Table *h = gco2t(l);
758 Node *n, *limit = gnodelast(h); 751 Node *n, *limit = gnodelast(h);
@@ -769,7 +762,9 @@ static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) {
769 if (isempty(gval(n))) /* is entry empty? */ 762 if (isempty(gval(n))) /* is entry empty? */
770 clearkey(n); /* clear its key */ 763 clearkey(n); /* clear its key */
771 } 764 }
765 work++;
772 } 766 }
767 return work;
773} 768}
774 769
775 770
@@ -781,6 +776,7 @@ static void freeupval (lua_State *L, UpVal *uv) {
781 776
782 777
783static void freeobj (lua_State *L, GCObject *o) { 778static void freeobj (lua_State *L, GCObject *o) {
779 G(L)->totalobjs--;
784 switch (o->tt) { 780 switch (o->tt) {
785 case LUA_VPROTO: 781 case LUA_VPROTO:
786 luaF_freeproto(L, gco2p(o)); 782 luaF_freeproto(L, gco2p(o));
@@ -830,10 +826,9 @@ static void freeobj (lua_State *L, GCObject *o) {
830** objects, where a dead object is one marked with the old (non current) 826** objects, where a dead object is one marked with the old (non current)
831** white; change all non-dead objects back to white, preparing for next 827** white; change all non-dead objects back to white, preparing for next
832** collection cycle. Return where to continue the traversal or NULL if 828** collection cycle. Return where to continue the traversal or NULL if
833** list is finished. ('*countout' gets the number of elements traversed.) 829** list is finished.
834*/ 830*/
835static GCObject **sweeplist (lua_State *L, GCObject **p, int countin, 831static GCObject **sweeplist (lua_State *L, GCObject **p, int countin) {
836 int *countout) {
837 global_State *g = G(L); 832 global_State *g = G(L);
838 int ow = otherwhite(g); 833 int ow = otherwhite(g);
839 int i; 834 int i;
@@ -850,8 +845,6 @@ static GCObject **sweeplist (lua_State *L, GCObject **p, int countin,
850 p = &curr->next; /* go to next element */ 845 p = &curr->next; /* go to next element */
851 } 846 }
852 } 847 }
853 if (countout)
854 *countout = i; /* number of elements traversed */
855 return (*p == NULL) ? NULL : p; 848 return (*p == NULL) ? NULL : p;
856} 849}
857 850
@@ -862,7 +855,7 @@ static GCObject **sweeplist (lua_State *L, GCObject **p, int countin,
862static GCObject **sweeptolive (lua_State *L, GCObject **p) { 855static GCObject **sweeptolive (lua_State *L, GCObject **p) {
863 GCObject **old = p; 856 GCObject **old = p;
864 do { 857 do {
865 p = sweeplist(L, p, 1, NULL); 858 p = sweeplist(L, p, 1);
866 } while (p == old); 859 } while (p == old);
867 return p; 860 return p;
868} 861}
@@ -881,11 +874,8 @@ static GCObject **sweeptolive (lua_State *L, GCObject **p) {
881*/ 874*/
882static void checkSizes (lua_State *L, global_State *g) { 875static void checkSizes (lua_State *L, global_State *g) {
883 if (!g->gcemergency) { 876 if (!g->gcemergency) {
884 if (g->strt.nuse < g->strt.size / 4) { /* string table too big? */ 877 if (g->strt.nuse < g->strt.size / 4) /* string table too big? */
885 l_mem olddebt = g->GCdebt;
886 luaS_resize(L, g->strt.size / 2); 878 luaS_resize(L, g->strt.size / 2);
887 g->GCestimate += g->GCdebt - olddebt; /* correct estimate */
888 }
889 } 879 }
890} 880}
891 881
@@ -944,18 +934,6 @@ static void GCTM (lua_State *L) {
944 934
945 935
946/* 936/*
947** Call a few finalizers
948*/
949static int runafewfinalizers (lua_State *L, int n) {
950 global_State *g = G(L);
951 int i;
952 for (i = 0; i < n && g->tobefnz; i++)
953 GCTM(L); /* call one finalizer */
954 return i;
955}
956
957
958/*
959** call all pending finalizers 937** call all pending finalizers
960*/ 938*/
961static void callallpendingfinalizers (lua_State *L) { 939static void callallpendingfinalizers (lua_State *L) {
@@ -1063,20 +1041,13 @@ void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) {
1063 1041
1064/* 1042/*
1065** Set the "time" to wait before starting a new GC cycle; cycle will 1043** Set the "time" to wait before starting a new GC cycle; cycle will
1066** start when memory use hits the threshold of ('estimate' * pause / 1044** start when number of objects in use hits the threshold of
1067** PAUSEADJ). (Division by 'estimate' should be OK: it cannot be zero, 1045** approximately (marked * pause / 100).
1068** because Lua cannot even start with less than PAUSEADJ bytes).
1069*/ 1046*/
1070static void setpause (global_State *g) { 1047static void setpause (global_State *g) {
1071 l_mem threshold, debt; 1048 l_obj threshold = applygcparam(g, gcpause, g->marked);
1072 int pause = getgcparam(g->gcpause); 1049 l_obj debt = threshold - gettotalobjs(g);
1073 l_mem estimate = g->GCestimate / PAUSEADJ; /* adjust 'estimate' */ 1050 if (debt < 0) debt = 0;
1074 lua_assert(estimate > 0);
1075 threshold = (pause < MAX_LMEM / estimate) /* overflow? */
1076 ? estimate * pause /* no overflow */
1077 : MAX_LMEM; /* overflow; truncate to maximum */
1078 debt = gettotalbytes(g) - threshold;
1079 if (debt > 0) debt = 0;
1080 luaE_setdebt(g, debt); 1051 luaE_setdebt(g, debt);
1081} 1052}
1082 1053
@@ -1316,18 +1287,17 @@ static void atomic2gen (lua_State *L, global_State *g) {
1316 sweep2old(L, &g->tobefnz); 1287 sweep2old(L, &g->tobefnz);
1317 1288
1318 g->gckind = KGC_GEN; 1289 g->gckind = KGC_GEN;
1319 g->lastatomic = 0; 1290 g->GClastmajor = gettotalobjs(g); /* base for memory control */
1320 g->GCestimate = gettotalbytes(g); /* base for memory control */
1321 finishgencycle(L, g); 1291 finishgencycle(L, g);
1322} 1292}
1323 1293
1324 1294
1325/* 1295/*
1326** Set debt for the next minor collection, which will happen when 1296** Set debt for the next minor collection, which will happen when
1327** memory grows 'genminormul'%. 1297** total number of objects grows 'genminormul'%.
1328*/ 1298*/
1329static void setminordebt (global_State *g) { 1299static void setminordebt (global_State *g) {
1330 luaE_setdebt(g, -(cast(l_mem, (gettotalbytes(g) / 100)) * g->genminormul)); 1300 luaE_setdebt(g, applygcparam(g, genminormul, gettotalobjs(g)));
1331} 1301}
1332 1302
1333 1303
@@ -1337,14 +1307,12 @@ static void setminordebt (global_State *g) {
1337** are cleared. Then, turn all objects into old and finishes the 1307** are cleared. Then, turn all objects into old and finishes the
1338** collection. 1308** collection.
1339*/ 1309*/
1340static lu_mem entergen (lua_State *L, global_State *g) { 1310static void entergen (lua_State *L, global_State *g) {
1341 lu_mem numobjs;
1342 luaC_runtilstate(L, bitmask(GCSpause)); /* prepare to start a new cycle */ 1311 luaC_runtilstate(L, bitmask(GCSpause)); /* prepare to start a new cycle */
1343 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */ 1312 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */
1344 numobjs = atomic(L); /* propagates all and then do the atomic stuff */ 1313 atomic(L); /* propagates all and then do the atomic stuff */
1345 atomic2gen(L, g); 1314 atomic2gen(L, g);
1346 setminordebt(g); /* set debt assuming next cycle will be minor */ 1315 setminordebt(g); /* set debt assuming next cycle will be minor */
1347 return numobjs;
1348} 1316}
1349 1317
1350 1318
@@ -1361,7 +1329,6 @@ static void enterinc (global_State *g) {
1361 g->finobjrold = g->finobjold1 = g->finobjsur = NULL; 1329 g->finobjrold = g->finobjold1 = g->finobjsur = NULL;
1362 g->gcstate = GCSpause; 1330 g->gcstate = GCSpause;
1363 g->gckind = KGC_INC; 1331 g->gckind = KGC_INC;
1364 g->lastatomic = 0;
1365} 1332}
1366 1333
1367 1334
@@ -1370,111 +1337,75 @@ static void enterinc (global_State *g) {
1370*/ 1337*/
1371void luaC_changemode (lua_State *L, int newmode) { 1338void luaC_changemode (lua_State *L, int newmode) {
1372 global_State *g = G(L); 1339 global_State *g = G(L);
1373 if (newmode != g->gckind) { 1340 if (newmode != g->gckind) { /* does it need to change? */
1374 if (newmode == KGC_GEN) /* entering generational mode? */ 1341 if (newmode == KGC_INC) { /* entering incremental mode? */
1342 if (g->gckind == KGC_GENMAJOR)
1343 g->gckind = KGC_INC; /* already incremental but in name */
1344 else
1345 enterinc(g); /* entering incremental mode */
1346 }
1347 else {
1348 lua_assert(newmode == KGC_GEN);
1375 entergen(L, g); 1349 entergen(L, g);
1376 else 1350 }
1377 enterinc(g); /* entering incremental mode */
1378 } 1351 }
1379 g->lastatomic = 0;
1380} 1352}
1381 1353
1382 1354
1383/* 1355/*
1384** Does a full collection in generational mode. 1356** Does a full collection in generational mode.
1385*/ 1357*/
1386static lu_mem fullgen (lua_State *L, global_State *g) { 1358static void fullgen (lua_State *L, global_State *g) {
1387 enterinc(g); 1359 enterinc(g);
1388 return entergen(L, g); 1360 entergen(L, g);
1389} 1361}
1390 1362
1391 1363
1392/* 1364/*
1393** Does a major collection after last collection was a "bad collection". 1365** Does a major collector up to the atomic phase and then either
1394** 1366** returns to minor collections or stays doing major ones. If the
1395** When the program is building a big structure, it allocates lots of 1367** number of objects collected this time (numobjs - marked) is more than
1396** memory but generates very little garbage. In those scenarios, 1368** half the number of objects created since the last major collection
1397** the generational mode just wastes time doing small collections, and 1369** (numobjs - lastmajor), it goes back to minor collections.
1398** major collections are frequently what we call a "bad collection", a 1370*/
1399** collection that frees too few objects. To avoid the cost of switching 1371static void genmajorstep (lua_State *L, global_State *g) {
1400** between generational mode and the incremental mode needed for full 1372 l_obj lastmajor = g->GClastmajor; /* count from last collection */
1401** (major) collections, the collector tries to stay in incremental mode 1373 l_obj numobjs = gettotalobjs(g); /* current count */
1402** after a bad collection, and to switch back to generational mode only
1403** after a "good" collection (one that traverses less than 9/8 objects
1404** of the previous one).
1405** The collector must choose whether to stay in incremental mode or to
1406** switch back to generational mode before sweeping. At this point, it
1407** does not know the real memory in use, so it cannot use memory to
1408** decide whether to return to generational mode. Instead, it uses the
1409** number of objects traversed (returned by 'atomic') as a proxy. The
1410** field 'g->lastatomic' keeps this count from the last collection.
1411** ('g->lastatomic != 0' also means that the last collection was bad.)
1412*/
1413static void stepgenfull (lua_State *L, global_State *g) {
1414 lu_mem newatomic; /* count of traversed objects */
1415 lu_mem lastatomic = g->lastatomic; /* count from last collection */
1416 if (g->gckind == KGC_GEN) /* still in generational mode? */
1417 enterinc(g); /* enter incremental mode */
1418 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */ 1374 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */
1419 newatomic = atomic(L); /* mark everybody */ 1375 atomic(L); /* mark everybody */
1420 if (newatomic < lastatomic + (lastatomic >> 3)) { /* good collection? */ 1376 if ((numobjs - g->marked) > ((numobjs - lastmajor) >> 1)) {
1421 atomic2gen(L, g); /* return to generational mode */ 1377 atomic2gen(L, g); /* return to generational mode */
1422 setminordebt(g); 1378 setminordebt(g);
1423 } 1379 }
1424 else { /* another bad collection; stay in incremental mode */ 1380 else { /* bad collection; stay in major mode */
1425 g->GCestimate = gettotalbytes(g); /* first estimate */
1426 entersweep(L); 1381 entersweep(L);
1427 luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */ 1382 luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */
1428 setpause(g); 1383 setpause(g);
1429 g->lastatomic = newatomic; 1384 g->GClastmajor = gettotalobjs(g);
1430 } 1385 }
1431} 1386}
1432 1387
1433 1388
1434/* 1389/*
1435** Does a generational "step". 1390** Does a generational "step". If the total number of objects grew
1436** Usually, this means doing a minor collection and setting the debt to 1391** more than 'majormul'% since the last major collection, does a
1437** make another collection when memory grows 'genminormul'% larger. 1392** major collection. Otherwise, does a minor collection.
1438**
1439** However, there are exceptions. If memory grows 'genmajormul'%
1440** larger than it was at the end of the last major collection (kept
1441** in 'g->GCestimate'), the function does a major collection. At the
1442** end, it checks whether the major collection was able to free a
1443** decent amount of memory (at least half the growth in memory since
1444** previous major collection). If so, the collector keeps its state,
1445** and the next collection will probably be minor again. Otherwise,
1446** we have what we call a "bad collection". In that case, set the field
1447** 'g->lastatomic' to signal that fact, so that the next collection will
1448** go to 'stepgenfull'.
1449**
1450** 'GCdebt <= 0' means an explicit call to GC step with "size" zero;
1451** in that case, do a minor collection.
1452*/ 1393*/
1453static void genstep (lua_State *L, global_State *g) { 1394static void genstep (lua_State *L, global_State *g) {
1454 if (g->lastatomic != 0) /* last collection was a bad one? */ 1395 l_obj majorbase = g->GClastmajor; /* count after last major collection */
1455 stepgenfull(L, g); /* do a full step */ 1396 l_obj majorinc = applygcparam(g, genmajormul, majorbase);
1456 else { 1397 if (gettotalobjs(g) > majorbase + majorinc && 0) {
1457 lu_mem majorbase = g->GCestimate; /* memory after last major collection */ 1398 /* do a major collection */
1458 lu_mem majorinc = (majorbase / 100) * getgcparam(g->genmajormul); 1399 enterinc(g);
1459 if (g->GCdebt > 0 && gettotalbytes(g) > majorbase + majorinc) { 1400 g->gckind = KGC_GENMAJOR;
1460 lu_mem numobjs = fullgen(L, g); /* do a major collection */ 1401 genmajorstep(L, g);
1461 if (gettotalbytes(g) < majorbase + (majorinc / 2)) { 1402 }
1462 /* collected at least half of memory growth since last major 1403 else { /* regular case; do a minor collection */
1463 collection; keep doing minor collections. */ 1404 g->marked = 0;
1464 lua_assert(g->lastatomic == 0); 1405 youngcollection(L, g);
1465 } 1406 setminordebt(g);
1466 else { /* bad collection */ 1407 lua_assert(g->GClastmajor == majorbase);
1467 g->lastatomic = numobjs; /* signal that last collection was bad */
1468 setpause(g); /* do a long wait for next (major) collection */
1469 }
1470 }
1471 else { /* regular case; do a minor collection */
1472 youngcollection(L, g);
1473 setminordebt(g);
1474 g->GCestimate = majorbase; /* preserve base value */
1475 }
1476 } 1408 }
1477 lua_assert(isdecGCmodegen(g));
1478} 1409}
1479 1410
1480/* }====================================================== */ 1411/* }====================================================== */
@@ -1533,9 +1464,9 @@ void luaC_freeallobjects (lua_State *L) {
1533} 1464}
1534 1465
1535 1466
1536static lu_mem atomic (lua_State *L) { 1467static l_obj atomic (lua_State *L) {
1468 l_obj work = 0;
1537 global_State *g = G(L); 1469 global_State *g = G(L);
1538 lu_mem work = 0;
1539 GCObject *origweak, *origall; 1470 GCObject *origweak, *origall;
1540 GCObject *grayagain = g->grayagain; /* save original list */ 1471 GCObject *grayagain = g->grayagain; /* save original list */
1541 g->grayagain = NULL; 1472 g->grayagain = NULL;
@@ -1552,50 +1483,44 @@ static lu_mem atomic (lua_State *L) {
1552 work += propagateall(g); /* propagate changes */ 1483 work += propagateall(g); /* propagate changes */
1553 g->gray = grayagain; 1484 g->gray = grayagain;
1554 work += propagateall(g); /* traverse 'grayagain' list */ 1485 work += propagateall(g); /* traverse 'grayagain' list */
1555 convergeephemerons(g); 1486 work += convergeephemerons(g);
1556 /* at this point, all strongly accessible objects are marked. */ 1487 /* at this point, all strongly accessible objects are marked. */
1557 /* Clear values from weak tables, before checking finalizers */ 1488 /* Clear values from weak tables, before checking finalizers */
1558 clearbyvalues(g, g->weak, NULL); 1489 work += clearbyvalues(g, g->weak, NULL);
1559 clearbyvalues(g, g->allweak, NULL); 1490 work += clearbyvalues(g, g->allweak, NULL);
1560 origweak = g->weak; origall = g->allweak; 1491 origweak = g->weak; origall = g->allweak;
1561 separatetobefnz(g, 0); /* separate objects to be finalized */ 1492 separatetobefnz(g, 0); /* separate objects to be finalized */
1562 work += markbeingfnz(g); /* mark objects that will be finalized */ 1493 work += markbeingfnz(g); /* mark objects that will be finalized */
1563 work += propagateall(g); /* remark, to propagate 'resurrection' */ 1494 work += propagateall(g); /* remark, to propagate 'resurrection' */
1564 convergeephemerons(g); 1495 work += convergeephemerons(g);
1565 /* at this point, all resurrected objects are marked. */ 1496 /* at this point, all resurrected objects are marked. */
1566 /* remove dead objects from weak tables */ 1497 /* remove dead objects from weak tables */
1567 clearbykeys(g, g->ephemeron); /* clear keys from all ephemeron tables */ 1498 work += clearbykeys(g, g->ephemeron); /* clear keys from all ephemeron */
1568 clearbykeys(g, g->allweak); /* clear keys from all 'allweak' tables */ 1499 work += clearbykeys(g, g->allweak); /* clear keys from all 'allweak' */
1569 /* clear values from resurrected weak tables */ 1500 /* clear values from resurrected weak tables */
1570 clearbyvalues(g, g->weak, origweak); 1501 work += clearbyvalues(g, g->weak, origweak);
1571 clearbyvalues(g, g->allweak, origall); 1502 work += clearbyvalues(g, g->allweak, origall);
1572 luaS_clearcache(g); 1503 luaS_clearcache(g);
1573 g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */ 1504 g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */
1574 lua_assert(g->gray == NULL); 1505 lua_assert(g->gray == NULL);
1575 return work; /* estimate of slots marked by 'atomic' */ 1506 return work;
1576} 1507}
1577 1508
1578 1509
1579static int sweepstep (lua_State *L, global_State *g, 1510static void sweepstep (lua_State *L, global_State *g,
1580 int nextstate, GCObject **nextlist) { 1511 int nextstate, GCObject **nextlist) {
1581 if (g->sweepgc) { 1512 if (g->sweepgc)
1582 l_mem olddebt = g->GCdebt; 1513 g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
1583 int count;
1584 g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX, &count);
1585 g->GCestimate += g->GCdebt - olddebt; /* update estimate */
1586 return count;
1587 }
1588 else { /* enter next state */ 1514 else { /* enter next state */
1589 g->gcstate = nextstate; 1515 g->gcstate = nextstate;
1590 g->sweepgc = nextlist; 1516 g->sweepgc = nextlist;
1591 return 0; /* no work done */
1592 } 1517 }
1593} 1518}
1594 1519
1595 1520
1596static lu_mem singlestep (lua_State *L) { 1521static l_obj singlestep (lua_State *L) {
1597 global_State *g = G(L); 1522 global_State *g = G(L);
1598 lu_mem work; 1523 l_obj work;
1599 lua_assert(!g->gcstopem); /* collector is not reentrant */ 1524 lua_assert(!g->gcstopem); /* collector is not reentrant */
1600 g->gcstopem = 1; /* no emergency collections while collecting */ 1525 g->gcstopem = 1; /* no emergency collections while collecting */
1601 switch (g->gcstate) { 1526 switch (g->gcstate) {
@@ -1610,26 +1535,30 @@ static lu_mem singlestep (lua_State *L) {
1610 g->gcstate = GCSenteratomic; /* finish propagate phase */ 1535 g->gcstate = GCSenteratomic; /* finish propagate phase */
1611 work = 0; 1536 work = 0;
1612 } 1537 }
1613 else 1538 else {
1614 work = propagatemark(g); /* traverse one gray object */ 1539 propagatemark(g); /* traverse one gray object */
1540 work = 1;
1541 }
1615 break; 1542 break;
1616 } 1543 }
1617 case GCSenteratomic: { 1544 case GCSenteratomic: {
1618 work = atomic(L); /* work is what was traversed by 'atomic' */ 1545 work = atomic(L);
1619 entersweep(L); 1546 entersweep(L);
1620 g->GCestimate = gettotalbytes(g); /* first estimate */
1621 break; 1547 break;
1622 } 1548 }
1623 case GCSswpallgc: { /* sweep "regular" objects */ 1549 case GCSswpallgc: { /* sweep "regular" objects */
1624 work = sweepstep(L, g, GCSswpfinobj, &g->finobj); 1550 sweepstep(L, g, GCSswpfinobj, &g->finobj);
1551 work = GCSWEEPMAX;
1625 break; 1552 break;
1626 } 1553 }
1627 case GCSswpfinobj: { /* sweep objects with finalizers */ 1554 case GCSswpfinobj: { /* sweep objects with finalizers */
1628 work = sweepstep(L, g, GCSswptobefnz, &g->tobefnz); 1555 sweepstep(L, g, GCSswptobefnz, &g->tobefnz);
1556 work = GCSWEEPMAX;
1629 break; 1557 break;
1630 } 1558 }
1631 case GCSswptobefnz: { /* sweep objects to be finalized */ 1559 case GCSswptobefnz: { /* sweep objects to be finalized */
1632 work = sweepstep(L, g, GCSswpend, NULL); 1560 sweepstep(L, g, GCSswpend, NULL);
1561 work = GCSWEEPMAX;
1633 break; 1562 break;
1634 } 1563 }
1635 case GCSswpend: { /* finish sweeps */ 1564 case GCSswpend: { /* finish sweeps */
@@ -1638,10 +1567,11 @@ static lu_mem singlestep (lua_State *L) {
1638 work = 0; 1567 work = 0;
1639 break; 1568 break;
1640 } 1569 }
1641 case GCScallfin: { /* call remaining finalizers */ 1570 case GCScallfin: { /* call finalizers */
1642 if (g->tobefnz && !g->gcemergency) { 1571 if (g->tobefnz && !g->gcemergency) {
1643 g->gcstopem = 0; /* ok collections during finalizers */ 1572 g->gcstopem = 0; /* ok collections during finalizers */
1644 work = runafewfinalizers(L, GCFINMAX) * GCFINALIZECOST; 1573 GCTM(L); /* call one finalizer */
1574 work = 1;
1645 } 1575 }
1646 else { /* emergency mode or no more finalizers */ 1576 else { /* emergency mode or no more finalizers */
1647 g->gcstate = GCSpause; /* finish collection */ 1577 g->gcstate = GCSpause; /* finish collection */
@@ -1676,20 +1606,16 @@ void luaC_runtilstate (lua_State *L, int statesmask) {
1676** controls when next step will be performed. 1606** controls when next step will be performed.
1677*/ 1607*/
1678static void incstep (lua_State *L, global_State *g) { 1608static void incstep (lua_State *L, global_State *g) {
1679 int stepmul = (getgcparam(g->gcstepmul) | 1); /* avoid division by 0 */ 1609 l_obj stepsize = cast(l_obj, 1) << g->gcstepsize;
1680 l_mem debt = (g->GCdebt / WORK2MEM) * stepmul; 1610 l_obj work2do = applygcparam(g, gcstepmul, stepsize);
1681 l_mem stepsize = (g->gcstepsize <= log2maxs(l_mem))
1682 ? ((cast(l_mem, 1) << g->gcstepsize) / WORK2MEM) * stepmul
1683 : MAX_LMEM; /* overflow; keep maximum value */
1684 do { /* repeat until pause or enough "credit" (negative debt) */ 1611 do { /* repeat until pause or enough "credit" (negative debt) */
1685 lu_mem work = singlestep(L); /* perform one single step */ 1612 l_obj work = singlestep(L); /* perform one single step */
1686 debt -= work; 1613 work2do -= work;
1687 } while (debt > -stepsize && g->gcstate != GCSpause); 1614 } while (work2do > 0 && g->gcstate != GCSpause);
1688 if (g->gcstate == GCSpause) 1615 if (g->gcstate == GCSpause)
1689 setpause(g); /* pause until next cycle */ 1616 setpause(g); /* pause until next cycle */
1690 else { 1617 else {
1691 debt = (debt / stepmul) * WORK2MEM; /* convert 'work units' to bytes */ 1618 luaE_setdebt(g, stepsize);
1692 luaE_setdebt(g, debt);
1693 } 1619 }
1694} 1620}
1695 1621
@@ -1700,13 +1626,21 @@ static void incstep (lua_State *L, global_State *g) {
1700*/ 1626*/
1701void luaC_step (lua_State *L) { 1627void luaC_step (lua_State *L) {
1702 global_State *g = G(L); 1628 global_State *g = G(L);
1629 lua_assert(!g->gcemergency);
1703 if (!gcrunning(g)) /* not running? */ 1630 if (!gcrunning(g)) /* not running? */
1704 luaE_setdebt(g, -2000); 1631 luaE_setdebt(g, 2000);
1705 else { 1632 else {
1706 if(isdecGCmodegen(g)) 1633 switch (g->gckind) {
1707 genstep(L, g); 1634 case KGC_INC:
1708 else 1635 incstep(L, g);
1709 incstep(L, g); 1636 break;
1637 case KGC_GEN:
1638 genstep(L, g);
1639 break;
1640 case KGC_GENMAJOR:
1641 genmajorstep(L, g);
1642 break;
1643 }
1710 } 1644 }
1711} 1645}
1712 1646
@@ -1726,8 +1660,8 @@ static void fullinc (lua_State *L, global_State *g) {
1726 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */ 1660 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */
1727 g->gcstate = GCSenteratomic; /* go straight to atomic phase ??? */ 1661 g->gcstate = GCSenteratomic; /* go straight to atomic phase ??? */
1728 luaC_runtilstate(L, bitmask(GCScallfin)); /* run up to finalizers */ 1662 luaC_runtilstate(L, bitmask(GCScallfin)); /* run up to finalizers */
1729 /* estimate must be correct after a full GC cycle */ 1663 /* 'marked' must be correct after a full GC cycle */
1730 lua_assert(g->GCestimate == gettotalbytes(g)); 1664 lua_assert(g->marked == gettotalobjs(g));
1731 luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */ 1665 luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */
1732 setpause(g); 1666 setpause(g);
1733} 1667}
@@ -1742,10 +1676,10 @@ void luaC_fullgc (lua_State *L, int isemergency) {
1742 global_State *g = G(L); 1676 global_State *g = G(L);
1743 lua_assert(!g->gcemergency); 1677 lua_assert(!g->gcemergency);
1744 g->gcemergency = isemergency; /* set flag */ 1678 g->gcemergency = isemergency; /* set flag */
1745 if (g->gckind == KGC_INC) 1679 if (g->gckind == KGC_GEN)
1746 fullinc(L, g);
1747 else
1748 fullgen(L, g); 1680 fullgen(L, g);
1681 else
1682 fullinc(L, g);
1749 g->gcemergency = 0; 1683 g->gcemergency = 0;
1750} 1684}
1751 1685