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 dd824e77..f68c5af0 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 */
@@ -105,7 +87,7 @@
105#define markobjectN(g,t) { if (t) markobject(g,t); } 87#define markobjectN(g,t) { if (t) markobject(g,t); }
106 88
107static void reallymarkobject (global_State *g, GCObject *o); 89static void reallymarkobject (global_State *g, GCObject *o);
108static lu_mem atomic (lua_State *L); 90static l_obj atomic (lua_State *L);
109static void entersweep (lua_State *L); 91static void entersweep (lua_State *L);
110 92
111 93
@@ -217,7 +199,7 @@ void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
217 } 199 }
218 else { /* sweep phase */ 200 else { /* sweep phase */
219 lua_assert(issweepphase(g)); 201 lua_assert(issweepphase(g));
220 if (g->gckind == KGC_INC) /* incremental mode? */ 202 if (g->gckind != KGC_GEN) /* incremental mode? */
221 makewhite(g, o); /* mark 'o' as white to avoid other barriers */ 203 makewhite(g, o); /* mark 'o' as white to avoid other barriers */
222 } 204 }
223} 205}
@@ -259,6 +241,7 @@ GCObject *luaC_newobjdt (lua_State *L, int tt, size_t sz, size_t offset) {
259 global_State *g = G(L); 241 global_State *g = G(L);
260 char *p = cast_charp(luaM_newobject(L, novariant(tt), sz)); 242 char *p = cast_charp(luaM_newobject(L, novariant(tt), sz));
261 GCObject *o = cast(GCObject *, p + offset); 243 GCObject *o = cast(GCObject *, p + offset);
244 g->GCdebt--;
262 o->marked = luaC_white(g); 245 o->marked = luaC_white(g);
263 o->tt = tt; 246 o->tt = tt;
264 o->next = g->allgc; 247 o->next = g->allgc;
@@ -267,6 +250,9 @@ GCObject *luaC_newobjdt (lua_State *L, int tt, size_t sz, size_t offset) {
267} 250}
268 251
269 252
253/*
254** create a new collectable object with no offset.
255*/
270GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) { 256GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
271 return luaC_newobjdt(L, tt, sz, 0); 257 return luaC_newobjdt(L, tt, sz, 0);
272} 258}
@@ -295,6 +281,7 @@ GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
295** (only closures can), and a userdata's metatable must be a table. 281** (only closures can), and a userdata's metatable must be a table.
296*/ 282*/
297static void reallymarkobject (global_State *g, GCObject *o) { 283static void reallymarkobject (global_State *g, GCObject *o) {
284 g->marked++;
298 switch (o->tt) { 285 switch (o->tt) {
299 case LUA_VSHRSTR: 286 case LUA_VSHRSTR:
300 case LUA_VLNGSTR: { 287 case LUA_VLNGSTR: {
@@ -342,9 +329,9 @@ static void markmt (global_State *g) {
342/* 329/*
343** mark all objects in list of being-finalized 330** mark all objects in list of being-finalized
344*/ 331*/
345static lu_mem markbeingfnz (global_State *g) { 332static l_obj markbeingfnz (global_State *g) {
346 GCObject *o; 333 GCObject *o;
347 lu_mem count = 0; 334 l_obj count = 0;
348 for (o = g->tobefnz; o != NULL; o = o->next) { 335 for (o = g->tobefnz; o != NULL; o = o->next) {
349 count++; 336 count++;
350 markobject(g, o); 337 markobject(g, o);
@@ -364,12 +351,11 @@ static lu_mem markbeingfnz (global_State *g) {
364** upvalues, as they have nothing to be checked. (If the thread gets an 351** upvalues, as they have nothing to be checked. (If the thread gets an
365** upvalue later, it will be linked in the list again.) 352** upvalue later, it will be linked in the list again.)
366*/ 353*/
367static int remarkupvals (global_State *g) { 354static l_obj remarkupvals (global_State *g) {
355 l_obj work = 0;
368 lua_State *thread; 356 lua_State *thread;
369 lua_State **p = &g->twups; 357 lua_State **p = &g->twups;
370 int work = 0; /* estimate of how much work was done here */
371 while ((thread = *p) != NULL) { 358 while ((thread = *p) != NULL) {
372 work++;
373 if (!iswhite(thread) && thread->openupval != NULL) 359 if (!iswhite(thread) && thread->openupval != NULL)
374 p = &thread->twups; /* keep marked thread with upvalues in the list */ 360 p = &thread->twups; /* keep marked thread with upvalues in the list */
375 else { /* thread is not marked or without upvalues */ 361 else { /* thread is not marked or without upvalues */
@@ -379,13 +365,13 @@ static int remarkupvals (global_State *g) {
379 thread->twups = thread; /* mark that it is out of list */ 365 thread->twups = thread; /* mark that it is out of list */
380 for (uv = thread->openupval; uv != NULL; uv = uv->u.open.next) { 366 for (uv = thread->openupval; uv != NULL; uv = uv->u.open.next) {
381 lua_assert(getage(uv) <= getage(thread)); 367 lua_assert(getage(uv) <= getage(thread));
382 work++;
383 if (!iswhite(uv)) { /* upvalue already visited? */ 368 if (!iswhite(uv)) { /* upvalue already visited? */
384 lua_assert(upisopen(uv) && isgray(uv)); 369 lua_assert(upisopen(uv) && isgray(uv));
385 markvalue(g, uv->v.p); /* mark its value */ 370 markvalue(g, uv->v.p); /* mark its value */
386 } 371 }
387 } 372 }
388 } 373 }
374 work++;
389 } 375 }
390 return work; 376 return work;
391} 377}
@@ -398,10 +384,15 @@ static void cleargraylists (global_State *g) {
398 384
399 385
400/* 386/*
401** mark root set and reset all gray lists, to start a new collection 387** mark root set and reset all gray lists, to start a new collection.
388** 'marked' is initialized with the number of fixed objects in the state,
389** to count the total number of live objects during a cycle. (That is
390** the metafield names, plus the reserved words, plus "_ENV" plus the
391** memory-error message.)
402*/ 392*/
403static void restartcollection (global_State *g) { 393static void restartcollection (global_State *g) {
404 cleargraylists(g); 394 cleargraylists(g);
395 g->marked = NFIXED;
405 markobject(g, g->mainthread); 396 markobject(g, g->mainthread);
406 markvalue(g, &g->l_registry); 397 markvalue(g, &g->l_registry);
407 markmt(g); 398 markmt(g);
@@ -539,7 +530,7 @@ static void traversestrongtable (global_State *g, Table *h) {
539} 530}
540 531
541 532
542static lu_mem traversetable (global_State *g, Table *h) { 533static void traversetable (global_State *g, Table *h) {
543 const char *weakkey, *weakvalue; 534 const char *weakkey, *weakvalue;
544 const TValue *mode = gfasttm(g, h->metatable, TM_MODE); 535 const TValue *mode = gfasttm(g, h->metatable, TM_MODE);
545 markobjectN(g, h->metatable); 536 markobjectN(g, h->metatable);
@@ -556,17 +547,15 @@ static lu_mem traversetable (global_State *g, Table *h) {
556 } 547 }
557 else /* not weak */ 548 else /* not weak */
558 traversestrongtable(g, h); 549 traversestrongtable(g, h);
559 return 1 + h->alimit + 2 * allocsizenode(h);
560} 550}
561 551
562 552
563static int traverseudata (global_State *g, Udata *u) { 553static void traverseudata (global_State *g, Udata *u) {
564 int i; 554 int i;
565 markobjectN(g, u->metatable); /* mark its metatable */ 555 markobjectN(g, u->metatable); /* mark its metatable */
566 for (i = 0; i < u->nuvalue; i++) 556 for (i = 0; i < u->nuvalue; i++)
567 markvalue(g, &u->uv[i].uv); 557 markvalue(g, &u->uv[i].uv);
568 genlink(g, obj2gco(u)); 558 genlink(g, obj2gco(u));
569 return 1 + u->nuvalue;
570} 559}
571 560
572 561
@@ -575,7 +564,7 @@ static int traverseudata (global_State *g, Udata *u) {
575** arrays can be larger than needed; the extra slots are filled with 564** arrays can be larger than needed; the extra slots are filled with
576** NULL, so the use of 'markobjectN') 565** NULL, so the use of 'markobjectN')
577*/ 566*/
578static int traverseproto (global_State *g, Proto *f) { 567static void traverseproto (global_State *g, Proto *f) {
579 int i; 568 int i;
580 markobjectN(g, f->source); 569 markobjectN(g, f->source);
581 for (i = 0; i < f->sizek; i++) /* mark literals */ 570 for (i = 0; i < f->sizek; i++) /* mark literals */
@@ -586,29 +575,26 @@ static int traverseproto (global_State *g, Proto *f) {
586 markobjectN(g, f->p[i]); 575 markobjectN(g, f->p[i]);
587 for (i = 0; i < f->sizelocvars; i++) /* mark local-variable names */ 576 for (i = 0; i < f->sizelocvars; i++) /* mark local-variable names */
588 markobjectN(g, f->locvars[i].varname); 577 markobjectN(g, f->locvars[i].varname);
589 return 1 + f->sizek + f->sizeupvalues + f->sizep + f->sizelocvars;
590} 578}
591 579
592 580
593static int traverseCclosure (global_State *g, CClosure *cl) { 581static void traverseCclosure (global_State *g, CClosure *cl) {
594 int i; 582 int i;
595 for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */ 583 for (i = 0; i < cl->nupvalues; i++) /* mark its upvalues */
596 markvalue(g, &cl->upvalue[i]); 584 markvalue(g, &cl->upvalue[i]);
597 return 1 + cl->nupvalues;
598} 585}
599 586
600/* 587/*
601** Traverse a Lua closure, marking its prototype and its upvalues. 588** Traverse a Lua closure, marking its prototype and its upvalues.
602** (Both can be NULL while closure is being created.) 589** (Both can be NULL while closure is being created.)
603*/ 590*/
604static int traverseLclosure (global_State *g, LClosure *cl) { 591static void traverseLclosure (global_State *g, LClosure *cl) {
605 int i; 592 int i;
606 markobjectN(g, cl->p); /* mark its prototype */ 593 markobjectN(g, cl->p); /* mark its prototype */
607 for (i = 0; i < cl->nupvalues; i++) { /* visit its upvalues */ 594 for (i = 0; i < cl->nupvalues; i++) { /* visit its upvalues */
608 UpVal *uv = cl->upvals[i]; 595 UpVal *uv = cl->upvals[i];
609 markobjectN(g, uv); /* mark upvalue */ 596 markobjectN(g, uv); /* mark upvalue */
610 } 597 }
611 return 1 + cl->nupvalues;
612} 598}
613 599
614 600
@@ -624,13 +610,13 @@ static int traverseLclosure (global_State *g, LClosure *cl) {
624** (which can only happen in generational mode) or if the traverse is in 610** (which can only happen in generational mode) or if the traverse is in
625** the propagate phase (which can only happen in incremental mode). 611** the propagate phase (which can only happen in incremental mode).
626*/ 612*/
627static int traversethread (global_State *g, lua_State *th) { 613static void traversethread (global_State *g, lua_State *th) {
628 UpVal *uv; 614 UpVal *uv;
629 StkId o = th->stack.p; 615 StkId o = th->stack.p;
630 if (isold(th) || g->gcstate == GCSpropagate) 616 if (isold(th) || g->gcstate == GCSpropagate)
631 linkgclist(th, g->grayagain); /* insert into 'grayagain' list */ 617 linkgclist(th, g->grayagain); /* insert into 'grayagain' list */
632 if (o == NULL) 618 if (o == NULL)
633 return 1; /* stack not completely built yet */ 619 return; /* stack not completely built yet */
634 lua_assert(g->gcstate == GCSatomic || 620 lua_assert(g->gcstate == GCSatomic ||
635 th->openupval == NULL || isintwups(th)); 621 th->openupval == NULL || isintwups(th));
636 for (; o < th->top.p; o++) /* mark live elements in the stack */ 622 for (; o < th->top.p; o++) /* mark live elements in the stack */
@@ -648,34 +634,35 @@ static int traversethread (global_State *g, lua_State *th) {
648 } 634 }
649 else if (!g->gcemergency) 635 else if (!g->gcemergency)
650 luaD_shrinkstack(th); /* do not change stack in emergency cycle */ 636 luaD_shrinkstack(th); /* do not change stack in emergency cycle */
651 return 1 + stacksize(th);
652} 637}
653 638
654 639
655/* 640/*
656** traverse one gray object, turning it to black. 641** traverse one gray object, turning it to black.
657*/ 642*/
658static lu_mem propagatemark (global_State *g) { 643static void propagatemark (global_State *g) {
659 GCObject *o = g->gray; 644 GCObject *o = g->gray;
660 nw2black(o); 645 nw2black(o);
661 g->gray = *getgclist(o); /* remove from 'gray' list */ 646 g->gray = *getgclist(o); /* remove from 'gray' list */
662 switch (o->tt) { 647 switch (o->tt) {
663 case LUA_VTABLE: return traversetable(g, gco2t(o)); 648 case LUA_VTABLE: traversetable(g, gco2t(o)); break;
664 case LUA_VUSERDATA: return traverseudata(g, gco2u(o)); 649 case LUA_VUSERDATA: traverseudata(g, gco2u(o)); break;
665 case LUA_VLCL: return traverseLclosure(g, gco2lcl(o)); 650 case LUA_VLCL: traverseLclosure(g, gco2lcl(o)); break;
666 case LUA_VCCL: return traverseCclosure(g, gco2ccl(o)); 651 case LUA_VCCL: traverseCclosure(g, gco2ccl(o)); break;
667 case LUA_VPROTO: return traverseproto(g, gco2p(o)); 652 case LUA_VPROTO: traverseproto(g, gco2p(o)); break;
668 case LUA_VTHREAD: return traversethread(g, gco2th(o)); 653 case LUA_VTHREAD: traversethread(g, gco2th(o)); break;
669 default: lua_assert(0); return 0; 654 default: lua_assert(0);
670 } 655 }
671} 656}
672 657
673 658
674static lu_mem propagateall (global_State *g) { 659static l_obj propagateall (global_State *g) {
675 lu_mem tot = 0; 660 l_obj work = 0;
676 while (g->gray) 661 while (g->gray) {
677 tot += propagatemark(g); 662 propagatemark(g);
678 return tot; 663 work++;
664 }
665 return work;
679} 666}
680 667
681 668
@@ -684,10 +671,10 @@ static lu_mem propagateall (global_State *g) {
684** Repeat until it converges, that is, nothing new is marked. 'dir' 671** Repeat until it converges, that is, nothing new is marked. 'dir'
685** inverts the direction of the traversals, trying to speed up 672** inverts the direction of the traversals, trying to speed up
686** convergence on chains in the same table. 673** convergence on chains in the same table.
687**
688*/ 674*/
689static void convergeephemerons (global_State *g) { 675static l_obj convergeephemerons (global_State *g) {
690 int changed; 676 int changed;
677 l_obj work = 0;
691 int dir = 0; 678 int dir = 0;
692 do { 679 do {
693 GCObject *w; 680 GCObject *w;
@@ -702,9 +689,11 @@ static void convergeephemerons (global_State *g) {
702 propagateall(g); /* propagate changes */ 689 propagateall(g); /* propagate changes */
703 changed = 1; /* will have to revisit all ephemeron tables */ 690 changed = 1; /* will have to revisit all ephemeron tables */
704 } 691 }
692 work++;
705 } 693 }
706 dir = !dir; /* invert direction next time */ 694 dir = !dir; /* invert direction next time */
707 } while (changed); /* repeat until no more changes */ 695 } while (changed); /* repeat until no more changes */
696 return work;
708} 697}
709 698
710/* }====================================================== */ 699/* }====================================================== */
@@ -720,7 +709,8 @@ static void convergeephemerons (global_State *g) {
720/* 709/*
721** clear entries with unmarked keys from all weaktables in list 'l' 710** clear entries with unmarked keys from all weaktables in list 'l'
722*/ 711*/
723static void clearbykeys (global_State *g, GCObject *l) { 712static l_obj clearbykeys (global_State *g, GCObject *l) {
713 l_obj work = 0;
724 for (; l; l = gco2t(l)->gclist) { 714 for (; l; l = gco2t(l)->gclist) {
725 Table *h = gco2t(l); 715 Table *h = gco2t(l);
726 Node *limit = gnodelast(h); 716 Node *limit = gnodelast(h);
@@ -731,7 +721,9 @@ static void clearbykeys (global_State *g, GCObject *l) {
731 if (isempty(gval(n))) /* is entry empty? */ 721 if (isempty(gval(n))) /* is entry empty? */
732 clearkey(n); /* clear its key */ 722 clearkey(n); /* clear its key */
733 } 723 }
724 work++;
734 } 725 }
726 return work;
735} 727}
736 728
737 729
@@ -739,7 +731,8 @@ static void clearbykeys (global_State *g, GCObject *l) {
739** clear entries with unmarked values from all weaktables in list 'l' up 731** clear entries with unmarked values from all weaktables in list 'l' up
740** to element 'f' 732** to element 'f'
741*/ 733*/
742static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) { 734static l_obj clearbyvalues (global_State *g, GCObject *l, GCObject *f) {
735 l_obj work = 0;
743 for (; l != f; l = gco2t(l)->gclist) { 736 for (; l != f; l = gco2t(l)->gclist) {
744 Table *h = gco2t(l); 737 Table *h = gco2t(l);
745 Node *n, *limit = gnodelast(h); 738 Node *n, *limit = gnodelast(h);
@@ -756,7 +749,9 @@ static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) {
756 if (isempty(gval(n))) /* is entry empty? */ 749 if (isempty(gval(n))) /* is entry empty? */
757 clearkey(n); /* clear its key */ 750 clearkey(n); /* clear its key */
758 } 751 }
752 work++;
759 } 753 }
754 return work;
760} 755}
761 756
762 757
@@ -768,6 +763,7 @@ static void freeupval (lua_State *L, UpVal *uv) {
768 763
769 764
770static void freeobj (lua_State *L, GCObject *o) { 765static void freeobj (lua_State *L, GCObject *o) {
766 G(L)->totalobjs--;
771 switch (o->tt) { 767 switch (o->tt) {
772 case LUA_VPROTO: 768 case LUA_VPROTO:
773 luaF_freeproto(L, gco2p(o)); 769 luaF_freeproto(L, gco2p(o));
@@ -817,10 +813,9 @@ static void freeobj (lua_State *L, GCObject *o) {
817** objects, where a dead object is one marked with the old (non current) 813** objects, where a dead object is one marked with the old (non current)
818** white; change all non-dead objects back to white, preparing for next 814** white; change all non-dead objects back to white, preparing for next
819** collection cycle. Return where to continue the traversal or NULL if 815** collection cycle. Return where to continue the traversal or NULL if
820** list is finished. ('*countout' gets the number of elements traversed.) 816** list is finished.
821*/ 817*/
822static GCObject **sweeplist (lua_State *L, GCObject **p, int countin, 818static GCObject **sweeplist (lua_State *L, GCObject **p, int countin) {
823 int *countout) {
824 global_State *g = G(L); 819 global_State *g = G(L);
825 int ow = otherwhite(g); 820 int ow = otherwhite(g);
826 int i; 821 int i;
@@ -837,8 +832,6 @@ static GCObject **sweeplist (lua_State *L, GCObject **p, int countin,
837 p = &curr->next; /* go to next element */ 832 p = &curr->next; /* go to next element */
838 } 833 }
839 } 834 }
840 if (countout)
841 *countout = i; /* number of elements traversed */
842 return (*p == NULL) ? NULL : p; 835 return (*p == NULL) ? NULL : p;
843} 836}
844 837
@@ -849,7 +842,7 @@ static GCObject **sweeplist (lua_State *L, GCObject **p, int countin,
849static GCObject **sweeptolive (lua_State *L, GCObject **p) { 842static GCObject **sweeptolive (lua_State *L, GCObject **p) {
850 GCObject **old = p; 843 GCObject **old = p;
851 do { 844 do {
852 p = sweeplist(L, p, 1, NULL); 845 p = sweeplist(L, p, 1);
853 } while (p == old); 846 } while (p == old);
854 return p; 847 return p;
855} 848}
@@ -868,11 +861,8 @@ static GCObject **sweeptolive (lua_State *L, GCObject **p) {
868*/ 861*/
869static void checkSizes (lua_State *L, global_State *g) { 862static void checkSizes (lua_State *L, global_State *g) {
870 if (!g->gcemergency) { 863 if (!g->gcemergency) {
871 if (g->strt.nuse < g->strt.size / 4) { /* string table too big? */ 864 if (g->strt.nuse < g->strt.size / 4) /* string table too big? */
872 l_mem olddebt = g->GCdebt;
873 luaS_resize(L, g->strt.size / 2); 865 luaS_resize(L, g->strt.size / 2);
874 g->GCestimate += g->GCdebt - olddebt; /* correct estimate */
875 }
876 } 866 }
877} 867}
878 868
@@ -931,18 +921,6 @@ static void GCTM (lua_State *L) {
931 921
932 922
933/* 923/*
934** Call a few finalizers
935*/
936static int runafewfinalizers (lua_State *L, int n) {
937 global_State *g = G(L);
938 int i;
939 for (i = 0; i < n && g->tobefnz; i++)
940 GCTM(L); /* call one finalizer */
941 return i;
942}
943
944
945/*
946** call all pending finalizers 924** call all pending finalizers
947*/ 925*/
948static void callallpendingfinalizers (lua_State *L) { 926static void callallpendingfinalizers (lua_State *L) {
@@ -1050,20 +1028,13 @@ void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) {
1050 1028
1051/* 1029/*
1052** Set the "time" to wait before starting a new GC cycle; cycle will 1030** Set the "time" to wait before starting a new GC cycle; cycle will
1053** start when memory use hits the threshold of ('estimate' * pause / 1031** start when number of objects in use hits the threshold of
1054** PAUSEADJ). (Division by 'estimate' should be OK: it cannot be zero, 1032** approximately (marked * pause / 100).
1055** because Lua cannot even start with less than PAUSEADJ bytes).
1056*/ 1033*/
1057static void setpause (global_State *g) { 1034static void setpause (global_State *g) {
1058 l_mem threshold, debt; 1035 l_obj threshold = applygcparam(g, gcpause, g->marked);
1059 int pause = getgcparam(g->gcpause); 1036 l_obj debt = threshold - gettotalobjs(g);
1060 l_mem estimate = g->GCestimate / PAUSEADJ; /* adjust 'estimate' */ 1037 if (debt < 0) debt = 0;
1061 lua_assert(estimate > 0);
1062 threshold = (pause < MAX_LMEM / estimate) /* overflow? */
1063 ? estimate * pause /* no overflow */
1064 : MAX_LMEM; /* overflow; truncate to maximum */
1065 debt = gettotalbytes(g) - threshold;
1066 if (debt > 0) debt = 0;
1067 luaE_setdebt(g, debt); 1038 luaE_setdebt(g, debt);
1068} 1039}
1069 1040
@@ -1303,18 +1274,17 @@ static void atomic2gen (lua_State *L, global_State *g) {
1303 sweep2old(L, &g->tobefnz); 1274 sweep2old(L, &g->tobefnz);
1304 1275
1305 g->gckind = KGC_GEN; 1276 g->gckind = KGC_GEN;
1306 g->lastatomic = 0; 1277 g->GClastmajor = gettotalobjs(g); /* base for memory control */
1307 g->GCestimate = gettotalbytes(g); /* base for memory control */
1308 finishgencycle(L, g); 1278 finishgencycle(L, g);
1309} 1279}
1310 1280
1311 1281
1312/* 1282/*
1313** Set debt for the next minor collection, which will happen when 1283** Set debt for the next minor collection, which will happen when
1314** memory grows 'genminormul'%. 1284** total number of objects grows 'genminormul'%.
1315*/ 1285*/
1316static void setminordebt (global_State *g) { 1286static void setminordebt (global_State *g) {
1317 luaE_setdebt(g, -(cast(l_mem, (gettotalbytes(g) / 100)) * g->genminormul)); 1287 luaE_setdebt(g, applygcparam(g, genminormul, gettotalobjs(g)));
1318} 1288}
1319 1289
1320 1290
@@ -1324,14 +1294,12 @@ static void setminordebt (global_State *g) {
1324** are cleared. Then, turn all objects into old and finishes the 1294** are cleared. Then, turn all objects into old and finishes the
1325** collection. 1295** collection.
1326*/ 1296*/
1327static lu_mem entergen (lua_State *L, global_State *g) { 1297static void entergen (lua_State *L, global_State *g) {
1328 lu_mem numobjs;
1329 luaC_runtilstate(L, bitmask(GCSpause)); /* prepare to start a new cycle */ 1298 luaC_runtilstate(L, bitmask(GCSpause)); /* prepare to start a new cycle */
1330 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */ 1299 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */
1331 numobjs = atomic(L); /* propagates all and then do the atomic stuff */ 1300 atomic(L); /* propagates all and then do the atomic stuff */
1332 atomic2gen(L, g); 1301 atomic2gen(L, g);
1333 setminordebt(g); /* set debt assuming next cycle will be minor */ 1302 setminordebt(g); /* set debt assuming next cycle will be minor */
1334 return numobjs;
1335} 1303}
1336 1304
1337 1305
@@ -1348,7 +1316,6 @@ static void enterinc (global_State *g) {
1348 g->finobjrold = g->finobjold1 = g->finobjsur = NULL; 1316 g->finobjrold = g->finobjold1 = g->finobjsur = NULL;
1349 g->gcstate = GCSpause; 1317 g->gcstate = GCSpause;
1350 g->gckind = KGC_INC; 1318 g->gckind = KGC_INC;
1351 g->lastatomic = 0;
1352} 1319}
1353 1320
1354 1321
@@ -1357,111 +1324,75 @@ static void enterinc (global_State *g) {
1357*/ 1324*/
1358void luaC_changemode (lua_State *L, int newmode) { 1325void luaC_changemode (lua_State *L, int newmode) {
1359 global_State *g = G(L); 1326 global_State *g = G(L);
1360 if (newmode != g->gckind) { 1327 if (newmode != g->gckind) { /* does it need to change? */
1361 if (newmode == KGC_GEN) /* entering generational mode? */ 1328 if (newmode == KGC_INC) { /* entering incremental mode? */
1329 if (g->gckind == KGC_GENMAJOR)
1330 g->gckind = KGC_INC; /* already incremental but in name */
1331 else
1332 enterinc(g); /* entering incremental mode */
1333 }
1334 else {
1335 lua_assert(newmode == KGC_GEN);
1362 entergen(L, g); 1336 entergen(L, g);
1363 else 1337 }
1364 enterinc(g); /* entering incremental mode */
1365 } 1338 }
1366 g->lastatomic = 0;
1367} 1339}
1368 1340
1369 1341
1370/* 1342/*
1371** Does a full collection in generational mode. 1343** Does a full collection in generational mode.
1372*/ 1344*/
1373static lu_mem fullgen (lua_State *L, global_State *g) { 1345static void fullgen (lua_State *L, global_State *g) {
1374 enterinc(g); 1346 enterinc(g);
1375 return entergen(L, g); 1347 entergen(L, g);
1376} 1348}
1377 1349
1378 1350
1379/* 1351/*
1380** Does a major collection after last collection was a "bad collection". 1352** Does a major collector up to the atomic phase and then either
1381** 1353** returns to minor collections or stays doing major ones. If the
1382** When the program is building a big structure, it allocates lots of 1354** number of objects collected this time (numobjs - marked) is more than
1383** memory but generates very little garbage. In those scenarios, 1355** half the number of objects created since the last major collection
1384** the generational mode just wastes time doing small collections, and 1356** (numobjs - lastmajor), it goes back to minor collections.
1385** major collections are frequently what we call a "bad collection", a 1357*/
1386** collection that frees too few objects. To avoid the cost of switching 1358static void genmajorstep (lua_State *L, global_State *g) {
1387** between generational mode and the incremental mode needed for full 1359 l_obj lastmajor = g->GClastmajor; /* count from last collection */
1388** (major) collections, the collector tries to stay in incremental mode 1360 l_obj numobjs = gettotalobjs(g); /* current count */
1389** after a bad collection, and to switch back to generational mode only
1390** after a "good" collection (one that traverses less than 9/8 objects
1391** of the previous one).
1392** The collector must choose whether to stay in incremental mode or to
1393** switch back to generational mode before sweeping. At this point, it
1394** does not know the real memory in use, so it cannot use memory to
1395** decide whether to return to generational mode. Instead, it uses the
1396** number of objects traversed (returned by 'atomic') as a proxy. The
1397** field 'g->lastatomic' keeps this count from the last collection.
1398** ('g->lastatomic != 0' also means that the last collection was bad.)
1399*/
1400static void stepgenfull (lua_State *L, global_State *g) {
1401 lu_mem newatomic; /* count of traversed objects */
1402 lu_mem lastatomic = g->lastatomic; /* count from last collection */
1403 if (g->gckind == KGC_GEN) /* still in generational mode? */
1404 enterinc(g); /* enter incremental mode */
1405 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */ 1361 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */
1406 newatomic = atomic(L); /* mark everybody */ 1362 atomic(L); /* mark everybody */
1407 if (newatomic < lastatomic + (lastatomic >> 3)) { /* good collection? */ 1363 if ((numobjs - g->marked) > ((numobjs - lastmajor) >> 1)) {
1408 atomic2gen(L, g); /* return to generational mode */ 1364 atomic2gen(L, g); /* return to generational mode */
1409 setminordebt(g); 1365 setminordebt(g);
1410 } 1366 }
1411 else { /* another bad collection; stay in incremental mode */ 1367 else { /* bad collection; stay in major mode */
1412 g->GCestimate = gettotalbytes(g); /* first estimate */
1413 entersweep(L); 1368 entersweep(L);
1414 luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */ 1369 luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */
1415 setpause(g); 1370 setpause(g);
1416 g->lastatomic = newatomic; 1371 g->GClastmajor = gettotalobjs(g);
1417 } 1372 }
1418} 1373}
1419 1374
1420 1375
1421/* 1376/*
1422** Does a generational "step". 1377** Does a generational "step". If the total number of objects grew
1423** Usually, this means doing a minor collection and setting the debt to 1378** more than 'majormul'% since the last major collection, does a
1424** make another collection when memory grows 'genminormul'% larger. 1379** major collection. Otherwise, does a minor collection.
1425**
1426** However, there are exceptions. If memory grows 'genmajormul'%
1427** larger than it was at the end of the last major collection (kept
1428** in 'g->GCestimate'), the function does a major collection. At the
1429** end, it checks whether the major collection was able to free a
1430** decent amount of memory (at least half the growth in memory since
1431** previous major collection). If so, the collector keeps its state,
1432** and the next collection will probably be minor again. Otherwise,
1433** we have what we call a "bad collection". In that case, set the field
1434** 'g->lastatomic' to signal that fact, so that the next collection will
1435** go to 'stepgenfull'.
1436**
1437** 'GCdebt <= 0' means an explicit call to GC step with "size" zero;
1438** in that case, do a minor collection.
1439*/ 1380*/
1440static void genstep (lua_State *L, global_State *g) { 1381static void genstep (lua_State *L, global_State *g) {
1441 if (g->lastatomic != 0) /* last collection was a bad one? */ 1382 l_obj majorbase = g->GClastmajor; /* count after last major collection */
1442 stepgenfull(L, g); /* do a full step */ 1383 l_obj majorinc = applygcparam(g, genmajormul, majorbase);
1443 else { 1384 if (gettotalobjs(g) > majorbase + majorinc && 0) {
1444 lu_mem majorbase = g->GCestimate; /* memory after last major collection */ 1385 /* do a major collection */
1445 lu_mem majorinc = (majorbase / 100) * getgcparam(g->genmajormul); 1386 enterinc(g);
1446 if (g->GCdebt > 0 && gettotalbytes(g) > majorbase + majorinc) { 1387 g->gckind = KGC_GENMAJOR;
1447 lu_mem numobjs = fullgen(L, g); /* do a major collection */ 1388 genmajorstep(L, g);
1448 if (gettotalbytes(g) < majorbase + (majorinc / 2)) { 1389 }
1449 /* collected at least half of memory growth since last major 1390 else { /* regular case; do a minor collection */
1450 collection; keep doing minor collections. */ 1391 g->marked = 0;
1451 lua_assert(g->lastatomic == 0); 1392 youngcollection(L, g);
1452 } 1393 setminordebt(g);
1453 else { /* bad collection */ 1394 lua_assert(g->GClastmajor == majorbase);
1454 g->lastatomic = numobjs; /* signal that last collection was bad */
1455 setpause(g); /* do a long wait for next (major) collection */
1456 }
1457 }
1458 else { /* regular case; do a minor collection */
1459 youngcollection(L, g);
1460 setminordebt(g);
1461 g->GCestimate = majorbase; /* preserve base value */
1462 }
1463 } 1395 }
1464 lua_assert(isdecGCmodegen(g));
1465} 1396}
1466 1397
1467/* }====================================================== */ 1398/* }====================================================== */
@@ -1520,9 +1451,9 @@ void luaC_freeallobjects (lua_State *L) {
1520} 1451}
1521 1452
1522 1453
1523static lu_mem atomic (lua_State *L) { 1454static l_obj atomic (lua_State *L) {
1455 l_obj work = 0;
1524 global_State *g = G(L); 1456 global_State *g = G(L);
1525 lu_mem work = 0;
1526 GCObject *origweak, *origall; 1457 GCObject *origweak, *origall;
1527 GCObject *grayagain = g->grayagain; /* save original list */ 1458 GCObject *grayagain = g->grayagain; /* save original list */
1528 g->grayagain = NULL; 1459 g->grayagain = NULL;
@@ -1539,50 +1470,44 @@ static lu_mem atomic (lua_State *L) {
1539 work += propagateall(g); /* propagate changes */ 1470 work += propagateall(g); /* propagate changes */
1540 g->gray = grayagain; 1471 g->gray = grayagain;
1541 work += propagateall(g); /* traverse 'grayagain' list */ 1472 work += propagateall(g); /* traverse 'grayagain' list */
1542 convergeephemerons(g); 1473 work += convergeephemerons(g);
1543 /* at this point, all strongly accessible objects are marked. */ 1474 /* at this point, all strongly accessible objects are marked. */
1544 /* Clear values from weak tables, before checking finalizers */ 1475 /* Clear values from weak tables, before checking finalizers */
1545 clearbyvalues(g, g->weak, NULL); 1476 work += clearbyvalues(g, g->weak, NULL);
1546 clearbyvalues(g, g->allweak, NULL); 1477 work += clearbyvalues(g, g->allweak, NULL);
1547 origweak = g->weak; origall = g->allweak; 1478 origweak = g->weak; origall = g->allweak;
1548 separatetobefnz(g, 0); /* separate objects to be finalized */ 1479 separatetobefnz(g, 0); /* separate objects to be finalized */
1549 work += markbeingfnz(g); /* mark objects that will be finalized */ 1480 work += markbeingfnz(g); /* mark objects that will be finalized */
1550 work += propagateall(g); /* remark, to propagate 'resurrection' */ 1481 work += propagateall(g); /* remark, to propagate 'resurrection' */
1551 convergeephemerons(g); 1482 work += convergeephemerons(g);
1552 /* at this point, all resurrected objects are marked. */ 1483 /* at this point, all resurrected objects are marked. */
1553 /* remove dead objects from weak tables */ 1484 /* remove dead objects from weak tables */
1554 clearbykeys(g, g->ephemeron); /* clear keys from all ephemeron tables */ 1485 work += clearbykeys(g, g->ephemeron); /* clear keys from all ephemeron */
1555 clearbykeys(g, g->allweak); /* clear keys from all 'allweak' tables */ 1486 work += clearbykeys(g, g->allweak); /* clear keys from all 'allweak' */
1556 /* clear values from resurrected weak tables */ 1487 /* clear values from resurrected weak tables */
1557 clearbyvalues(g, g->weak, origweak); 1488 work += clearbyvalues(g, g->weak, origweak);
1558 clearbyvalues(g, g->allweak, origall); 1489 work += clearbyvalues(g, g->allweak, origall);
1559 luaS_clearcache(g); 1490 luaS_clearcache(g);
1560 g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */ 1491 g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */
1561 lua_assert(g->gray == NULL); 1492 lua_assert(g->gray == NULL);
1562 return work; /* estimate of slots marked by 'atomic' */ 1493 return work;
1563} 1494}
1564 1495
1565 1496
1566static int sweepstep (lua_State *L, global_State *g, 1497static void sweepstep (lua_State *L, global_State *g,
1567 int nextstate, GCObject **nextlist) { 1498 int nextstate, GCObject **nextlist) {
1568 if (g->sweepgc) { 1499 if (g->sweepgc)
1569 l_mem olddebt = g->GCdebt; 1500 g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
1570 int count;
1571 g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX, &count);
1572 g->GCestimate += g->GCdebt - olddebt; /* update estimate */
1573 return count;
1574 }
1575 else { /* enter next state */ 1501 else { /* enter next state */
1576 g->gcstate = nextstate; 1502 g->gcstate = nextstate;
1577 g->sweepgc = nextlist; 1503 g->sweepgc = nextlist;
1578 return 0; /* no work done */
1579 } 1504 }
1580} 1505}
1581 1506
1582 1507
1583static lu_mem singlestep (lua_State *L) { 1508static l_obj singlestep (lua_State *L) {
1584 global_State *g = G(L); 1509 global_State *g = G(L);
1585 lu_mem work; 1510 l_obj work;
1586 lua_assert(!g->gcstopem); /* collector is not reentrant */ 1511 lua_assert(!g->gcstopem); /* collector is not reentrant */
1587 g->gcstopem = 1; /* no emergency collections while collecting */ 1512 g->gcstopem = 1; /* no emergency collections while collecting */
1588 switch (g->gcstate) { 1513 switch (g->gcstate) {
@@ -1597,26 +1522,30 @@ static lu_mem singlestep (lua_State *L) {
1597 g->gcstate = GCSenteratomic; /* finish propagate phase */ 1522 g->gcstate = GCSenteratomic; /* finish propagate phase */
1598 work = 0; 1523 work = 0;
1599 } 1524 }
1600 else 1525 else {
1601 work = propagatemark(g); /* traverse one gray object */ 1526 propagatemark(g); /* traverse one gray object */
1527 work = 1;
1528 }
1602 break; 1529 break;
1603 } 1530 }
1604 case GCSenteratomic: { 1531 case GCSenteratomic: {
1605 work = atomic(L); /* work is what was traversed by 'atomic' */ 1532 work = atomic(L);
1606 entersweep(L); 1533 entersweep(L);
1607 g->GCestimate = gettotalbytes(g); /* first estimate */
1608 break; 1534 break;
1609 } 1535 }
1610 case GCSswpallgc: { /* sweep "regular" objects */ 1536 case GCSswpallgc: { /* sweep "regular" objects */
1611 work = sweepstep(L, g, GCSswpfinobj, &g->finobj); 1537 sweepstep(L, g, GCSswpfinobj, &g->finobj);
1538 work = GCSWEEPMAX;
1612 break; 1539 break;
1613 } 1540 }
1614 case GCSswpfinobj: { /* sweep objects with finalizers */ 1541 case GCSswpfinobj: { /* sweep objects with finalizers */
1615 work = sweepstep(L, g, GCSswptobefnz, &g->tobefnz); 1542 sweepstep(L, g, GCSswptobefnz, &g->tobefnz);
1543 work = GCSWEEPMAX;
1616 break; 1544 break;
1617 } 1545 }
1618 case GCSswptobefnz: { /* sweep objects to be finalized */ 1546 case GCSswptobefnz: { /* sweep objects to be finalized */
1619 work = sweepstep(L, g, GCSswpend, NULL); 1547 sweepstep(L, g, GCSswpend, NULL);
1548 work = GCSWEEPMAX;
1620 break; 1549 break;
1621 } 1550 }
1622 case GCSswpend: { /* finish sweeps */ 1551 case GCSswpend: { /* finish sweeps */
@@ -1625,10 +1554,11 @@ static lu_mem singlestep (lua_State *L) {
1625 work = 0; 1554 work = 0;
1626 break; 1555 break;
1627 } 1556 }
1628 case GCScallfin: { /* call remaining finalizers */ 1557 case GCScallfin: { /* call finalizers */
1629 if (g->tobefnz && !g->gcemergency) { 1558 if (g->tobefnz && !g->gcemergency) {
1630 g->gcstopem = 0; /* ok collections during finalizers */ 1559 g->gcstopem = 0; /* ok collections during finalizers */
1631 work = runafewfinalizers(L, GCFINMAX) * GCFINALIZECOST; 1560 GCTM(L); /* call one finalizer */
1561 work = 1;
1632 } 1562 }
1633 else { /* emergency mode or no more finalizers */ 1563 else { /* emergency mode or no more finalizers */
1634 g->gcstate = GCSpause; /* finish collection */ 1564 g->gcstate = GCSpause; /* finish collection */
@@ -1663,20 +1593,16 @@ void luaC_runtilstate (lua_State *L, int statesmask) {
1663** controls when next step will be performed. 1593** controls when next step will be performed.
1664*/ 1594*/
1665static void incstep (lua_State *L, global_State *g) { 1595static void incstep (lua_State *L, global_State *g) {
1666 int stepmul = (getgcparam(g->gcstepmul) | 1); /* avoid division by 0 */ 1596 l_obj stepsize = cast(l_obj, 1) << g->gcstepsize;
1667 l_mem debt = (g->GCdebt / WORK2MEM) * stepmul; 1597 l_obj work2do = applygcparam(g, gcstepmul, stepsize);
1668 l_mem stepsize = (g->gcstepsize <= log2maxs(l_mem))
1669 ? ((cast(l_mem, 1) << g->gcstepsize) / WORK2MEM) * stepmul
1670 : MAX_LMEM; /* overflow; keep maximum value */
1671 do { /* repeat until pause or enough "credit" (negative debt) */ 1598 do { /* repeat until pause or enough "credit" (negative debt) */
1672 lu_mem work = singlestep(L); /* perform one single step */ 1599 l_obj work = singlestep(L); /* perform one single step */
1673 debt -= work; 1600 work2do -= work;
1674 } while (debt > -stepsize && g->gcstate != GCSpause); 1601 } while (work2do > 0 && g->gcstate != GCSpause);
1675 if (g->gcstate == GCSpause) 1602 if (g->gcstate == GCSpause)
1676 setpause(g); /* pause until next cycle */ 1603 setpause(g); /* pause until next cycle */
1677 else { 1604 else {
1678 debt = (debt / stepmul) * WORK2MEM; /* convert 'work units' to bytes */ 1605 luaE_setdebt(g, stepsize);
1679 luaE_setdebt(g, debt);
1680 } 1606 }
1681} 1607}
1682 1608
@@ -1687,13 +1613,21 @@ static void incstep (lua_State *L, global_State *g) {
1687*/ 1613*/
1688void luaC_step (lua_State *L) { 1614void luaC_step (lua_State *L) {
1689 global_State *g = G(L); 1615 global_State *g = G(L);
1616 lua_assert(!g->gcemergency);
1690 if (!gcrunning(g)) /* not running? */ 1617 if (!gcrunning(g)) /* not running? */
1691 luaE_setdebt(g, -2000); 1618 luaE_setdebt(g, 2000);
1692 else { 1619 else {
1693 if(isdecGCmodegen(g)) 1620 switch (g->gckind) {
1694 genstep(L, g); 1621 case KGC_INC:
1695 else 1622 incstep(L, g);
1696 incstep(L, g); 1623 break;
1624 case KGC_GEN:
1625 genstep(L, g);
1626 break;
1627 case KGC_GENMAJOR:
1628 genmajorstep(L, g);
1629 break;
1630 }
1697 } 1631 }
1698} 1632}
1699 1633
@@ -1711,8 +1645,8 @@ static void fullinc (lua_State *L, global_State *g) {
1711 /* finish any pending sweep phase to start a new cycle */ 1645 /* finish any pending sweep phase to start a new cycle */
1712 luaC_runtilstate(L, bitmask(GCSpause)); 1646 luaC_runtilstate(L, bitmask(GCSpause));
1713 luaC_runtilstate(L, bitmask(GCScallfin)); /* run up to finalizers */ 1647 luaC_runtilstate(L, bitmask(GCScallfin)); /* run up to finalizers */
1714 /* estimate must be correct after a full GC cycle */ 1648 /* 'marked' must be correct after a full GC cycle */
1715 lua_assert(g->GCestimate == gettotalbytes(g)); 1649 lua_assert(g->marked == gettotalobjs(g));
1716 luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */ 1650 luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */
1717 setpause(g); 1651 setpause(g);
1718} 1652}
@@ -1727,10 +1661,10 @@ void luaC_fullgc (lua_State *L, int isemergency) {
1727 global_State *g = G(L); 1661 global_State *g = G(L);
1728 lua_assert(!g->gcemergency); 1662 lua_assert(!g->gcemergency);
1729 g->gcemergency = isemergency; /* set flag */ 1663 g->gcemergency = isemergency; /* set flag */
1730 if (g->gckind == KGC_INC) 1664 if (g->gckind == KGC_GEN)
1731 fullinc(L, g);
1732 else
1733 fullgen(L, g); 1665 fullgen(L, g);
1666 else
1667 fullinc(L, g);
1734 g->gcemergency = 0; 1668 g->gcemergency = 0;
1735} 1669}
1736 1670