aboutsummaryrefslogtreecommitdiff
path: root/lgc.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2017-02-23 18:07:34 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2017-02-23 18:07:34 -0300
commitf5f3df3bd17fb3489bbd26ab39fe1580a8dbf9c9 (patch)
tree84f67f71a728bc988661349c361f2a968b1d4910 /lgc.c
parente6c1e6005a9346d378e004a6d6e7fd98c7ee191b (diff)
downloadlua-f5f3df3bd17fb3489bbd26ab39fe1580a8dbf9c9.tar.gz
lua-f5f3df3bd17fb3489bbd26ab39fe1580a8dbf9c9.tar.bz2
lua-f5f3df3bd17fb3489bbd26ab39fe1580a8dbf9c9.zip
generational collection: new attempt (still incomplete)
Diffstat (limited to 'lgc.c')
-rw-r--r--lgc.c183
1 files changed, 159 insertions, 24 deletions
diff --git a/lgc.c b/lgc.c
index de3f2a21..44e5dc31 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: lgc.c,v 2.214 2016/11/07 12:38:35 roberto Exp roberto $ 2** $Id: lgc.c,v 2.215 2016/12/22 13:08:50 roberto Exp roberto $
3** Garbage Collector 3** Garbage Collector
4** See Copyright Notice in lua.h 4** See Copyright Notice in lua.h
5*/ 5*/
@@ -59,11 +59,10 @@
59#define PAUSEADJ 100 59#define PAUSEADJ 100
60 60
61 61
62/* 62/* mask to erase all color bits */
63** 'makewhite' erases all color bits then sets only the current white
64** bit
65*/
66#define maskcolors (~(bitmask(BLACKBIT) | WHITEBITS)) 63#define maskcolors (~(bitmask(BLACKBIT) | WHITEBITS))
64
65/* macro to erase all color bits then sets only the current white bit */
67#define makewhite(g,x) \ 66#define makewhite(g,x) \
68 (x->marked = cast_byte((x->marked & maskcolors) | luaC_white(g))) 67 (x->marked = cast_byte((x->marked & maskcolors) | luaC_white(g)))
69 68
@@ -92,6 +91,7 @@
92#define markobjectN(g,t) { if (t) markobject(g,t); } 91#define markobjectN(g,t) { if (t) markobject(g,t); }
93 92
94static void reallymarkobject (global_State *g, GCObject *o); 93static void reallymarkobject (global_State *g, GCObject *o);
94static l_mem atomic (lua_State *L);
95 95
96 96
97/* 97/*
@@ -155,8 +155,11 @@ static int iscleared (global_State *g, const TValue *o) {
155void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) { 155void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
156 global_State *g = G(L); 156 global_State *g = G(L);
157 lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o)); 157 lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
158 if (keepinvariant(g)) /* must keep invariant? */ 158 if (keepinvariant(g)) { /* must keep invariant? */
159 reallymarkobject(g, v); /* restore invariant */ 159 reallymarkobject(g, v); /* restore invariant */
160 if (isold(o))
161 l_setbit((v)->marked, OLDBIT);
162 }
160 else { /* sweep phase */ 163 else { /* sweep phase */
161 lua_assert(issweepphase(g)); 164 lua_assert(issweepphase(g));
162 makewhite(g, o); /* mark main obj. as white to avoid other barriers */ 165 makewhite(g, o); /* mark main obj. as white to avoid other barriers */
@@ -186,8 +189,10 @@ void luaC_upvalbarrier_ (lua_State *L, UpVal *uv) {
186 global_State *g = G(L); 189 global_State *g = G(L);
187 GCObject *o = gcvalue(uv->v); 190 GCObject *o = gcvalue(uv->v);
188 lua_assert(!upisopen(uv)); /* ensured by macro luaC_upvalbarrier */ 191 lua_assert(!upisopen(uv)); /* ensured by macro luaC_upvalbarrier */
189 if (keepinvariant(g)) 192 if (keepinvariant(g)) {
190 markobject(g, o); 193 markobject(g, o);
194 l_setbit((o)->marked, OLDBIT);
195 }
191} 196}
192 197
193 198
@@ -922,6 +927,121 @@ void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) {
922/* }====================================================== */ 927/* }====================================================== */
923 928
924 929
930/*
931** {======================================================
932** Generational Collector
933** =======================================================
934*/
935
936
937#if 0
938static int count (GCObject *p, GCObject *limit) {
939 int res = 0;
940 for (; p != NULL && p != limit; p = p->next)
941 res++;
942 return res;
943}
944#endif
945
946
947static GCObject **sweepgen (lua_State *L, GCObject **p, GCObject *limit,
948 int zeromask, int onemask) {
949 global_State *g = G(L);
950 int ow = otherwhite(g);
951 GCObject *curr;
952 while ((curr = *p) != limit) {
953 int marked = curr->marked;
954 if (isdeadm(ow, marked)) { /* is 'curr' dead? */
955 lua_assert(!isold(curr));
956 *p = curr->next; /* remove 'curr' from list */
957 freeobj(L, curr); /* erase 'curr' */
958 }
959 else { /* correct mark */
960 if (!isold(curr)) /* don't change old objects */
961 curr->marked = cast_byte((marked & zeromask) | onemask);
962 p = &curr->next; /* go to next element */
963 }
964 }
965 return p;
966}
967
968
969static void startgencycle (lua_State *L, global_State *g) {
970 propagateall(g);
971 atomic(L);
972}
973
974
975static void finishgencycle (lua_State *L, global_State *g, int mask) {
976 sweepgen(L, &g->finobj, NULL, ~0, mask);
977 sweepgen(L, &g->tobefnz, NULL, ~0, mask);
978 checkSizes(L, g);
979 g->gcstate = GCSpropagate; /* skip restart */
980 callallpendingfinalizers(L);
981}
982
983
984static void youngcollection (lua_State *L, global_State *g) {
985 GCObject **psurvival;
986 lua_assert(g->gcstate == GCSpropagate);
987 startgencycle(L, g);
988 /* sweep nursery */
989 psurvival = sweepgen(L, &g->allgc, g->survival, maskcolors, luaC_white(g));
990 lua_assert(*psurvival == g->survival);
991 /* sweep 'survival' list, making elements old */
992 sweepgen(L, psurvival, g->old, ~0, bitmask(OLDBIT));
993 /* incorporate 'survival' list into old list */
994 g->old = *psurvival;
995 /* surviving young objects go to 'survival' list */
996 g->survival = g->allgc;
997 finishgencycle(L, g, 0);
998lua_checkmemory(L);
999}
1000
1001
1002static void entergen (lua_State *L, global_State *g) {
1003lua_checkmemory(L);
1004 lua_assert(g->old == NULL && g->survival == NULL);
1005 luaC_runtilstate(L, bitmask(GCSpause)); /* prepare to start a new cycle */
1006 luaC_runtilstate(L, bitmask(GCSpropagate)); /* start new cycle */
1007 startgencycle(L, g);
1008 /* sweep all ellements making them old */
1009 sweepgen(L, &g->allgc, g->survival, ~0, bitmask(OLDBIT));
1010 /* everything alive now is old; 'survival' is empty */
1011 g->old = g->survival = g->allgc;
1012 finishgencycle(L, g, bitmask(OLDBIT));
1013lua_checkmemory(L);
1014}
1015
1016
1017void luaC_changemode (lua_State *L, int newmode) {
1018 global_State *g = G(L);
1019 if (newmode != g->gckind) { /* otherwise, nothing to be done */
1020 if (newmode == KGC_GEN) /* entering generational mode? */
1021 entergen(L, g);
1022 else { /* entering incremental mode */
1023lua_checkmemory(L);
1024 youngcollection(L, g);
1025 g->old = g->survival = NULL;
1026lua_checkmemory(L);
1027 }
1028 g->gckind = newmode;
1029 }
1030}
1031
1032
1033static void genstep (lua_State *L, global_State *g) {
1034 lu_mem mem;
1035 youngcollection(L, g);
1036 mem = gettotalbytes(g);
1037 luaE_setdebt(g, -((mem / 100) * 20));
1038}
1039
1040
1041
1042
1043/* }====================================================== */
1044
925 1045
926/* 1046/*
927** {====================================================== 1047** {======================================================
@@ -963,17 +1083,24 @@ static void entersweep (lua_State *L) {
963} 1083}
964 1084
965 1085
1086static void deletealllist (lua_State *L, GCObject *p) {
1087 while (p) {
1088 GCObject *next = p->next;
1089 freeobj(L, p);
1090 p = next;
1091 }
1092}
1093
1094
966void luaC_freeallobjects (lua_State *L) { 1095void luaC_freeallobjects (lua_State *L) {
967 global_State *g = G(L); 1096 global_State *g = G(L);
968 separatetobefnz(g, 1); /* separate all objects with finalizers */ 1097 separatetobefnz(g, 1); /* separate all objects with finalizers */
969 lua_assert(g->finobj == NULL); 1098 lua_assert(g->finobj == NULL);
970 callallpendingfinalizers(L); 1099 callallpendingfinalizers(L);
971 lua_assert(g->tobefnz == NULL); 1100 lua_assert(g->tobefnz == NULL);
972 g->currentwhite = WHITEBITS; /* this "white" makes all objects look dead */ 1101 deletealllist(L, g->finobj);
973 g->gckind = KGC_NORMAL; 1102 deletealllist(L, g->allgc);
974 sweepwholelist(L, &g->finobj); 1103 deletealllist(L, g->fixedgc); /* collect fixed objects */
975 sweepwholelist(L, &g->allgc);
976 sweepwholelist(L, &g->fixedgc); /* collect fixed objects */
977 lua_assert(g->strt.nuse == 0); 1104 lua_assert(g->strt.nuse == 0);
978} 1105}
979 1106
@@ -996,6 +1123,7 @@ static l_mem atomic (lua_State *L) {
996 propagateall(g); /* propagate changes */ 1123 propagateall(g); /* propagate changes */
997 work = g->GCmemtrav; /* stop counting (do not recount 'grayagain') */ 1124 work = g->GCmemtrav; /* stop counting (do not recount 'grayagain') */
998 g->gray = grayagain; 1125 g->gray = grayagain;
1126 g->grayagain = NULL;
999 propagateall(g); /* traverse 'grayagain' list */ 1127 propagateall(g); /* traverse 'grayagain' list */
1000 g->GCmemtrav = 0; /* restart counting */ 1128 g->GCmemtrav = 0; /* restart counting */
1001 convergeephemerons(g); 1129 convergeephemerons(g);
@@ -1052,10 +1180,10 @@ static lu_mem singlestep (lua_State *L) {
1052 } 1180 }
1053 case GCSpropagate: { 1181 case GCSpropagate: {
1054 g->GCmemtrav = 0; 1182 g->GCmemtrav = 0;
1055 lua_assert(g->gray); 1183 if (g->gray == NULL) /* no more gray objects? */
1056 propagatemark(g);
1057 if (g->gray == NULL) /* no more gray objects? */
1058 g->gcstate = GCSatomic; /* finish propagate phase */ 1184 g->gcstate = GCSatomic; /* finish propagate phase */
1185 else
1186 propagatemark(g); /* traverse one gray object */
1059 return g->GCmemtrav; /* memory traversed in this step */ 1187 return g->GCmemtrav; /* memory traversed in this step */
1060 } 1188 }
1061 case GCSatomic: { 1189 case GCSatomic: {
@@ -1123,15 +1251,10 @@ static l_mem getdebt (global_State *g) {
1123} 1251}
1124 1252
1125/* 1253/*
1126** performs a basic GC step when collector is running 1254** performs a basic incremental step
1127*/ 1255*/
1128void luaC_step (lua_State *L) { 1256static void incstep (lua_State *L, global_State *g) {
1129 global_State *g = G(L); 1257 l_mem debt = getdebt(g); /* GC deficit (to be paid now) */
1130 l_mem debt = getdebt(g); /* GC deficit (be paid now) */
1131 if (!g->gcrunning) { /* not running? */
1132 luaE_setdebt(g, -GCSTEPSIZE * 10); /* avoid being called too often */
1133 return;
1134 }
1135 do { /* repeat until pause or enough "credit" (negative debt) */ 1258 do { /* repeat until pause or enough "credit" (negative debt) */
1136 lu_mem work = singlestep(L); /* perform one single step */ 1259 lu_mem work = singlestep(L); /* perform one single step */
1137 debt -= work; 1260 debt -= work;
@@ -1145,6 +1268,19 @@ void luaC_step (lua_State *L) {
1145 } 1268 }
1146} 1269}
1147 1270
1271/*
1272** performs a basic GC step when collector is running
1273*/
1274void luaC_step (lua_State *L) {
1275 global_State *g = G(L);
1276 if (!g->gcrunning) /* not running? */
1277 luaE_setdebt(g, -GCSTEPSIZE * 10); /* avoid being called too often */
1278 else if (g->gckind == KGC_NORMAL)
1279 incstep(L, g);
1280 else
1281 genstep(L, g);
1282}
1283
1148 1284
1149/* 1285/*
1150** Performs a full GC cycle; if 'isemergency', set a flag to avoid 1286** Performs a full GC cycle; if 'isemergency', set a flag to avoid
@@ -1164,7 +1300,6 @@ void luaC_fullgc (lua_State *L, int isemergency) {
1164 } 1300 }
1165 /* finish any pending sweep phase to start a new cycle */ 1301 /* finish any pending sweep phase to start a new cycle */
1166 luaC_runtilstate(L, bitmask(GCSpause)); 1302 luaC_runtilstate(L, bitmask(GCSpause));
1167 luaC_runtilstate(L, ~bitmask(GCSpause)); /* start new collection */
1168 luaC_runtilstate(L, bitmask(GCScallfin)); /* run up to finalizers */ 1303 luaC_runtilstate(L, bitmask(GCScallfin)); /* run up to finalizers */
1169 /* estimate must be correct after a full GC cycle */ 1304 /* estimate must be correct after a full GC cycle */
1170 lua_assert(g->GCestimate == gettotalbytes(g)); 1305 lua_assert(g->GCestimate == gettotalbytes(g));
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-16 23:55:28 +0000