aboutsummaryrefslogtreecommitdiff
path: root/lgc.c
diff options
context:
space:
mode:
Diffstat (limited to 'lgc.c')
-rw-r--r--lgc.c143
1 files changed, 67 insertions, 76 deletions
diff --git a/lgc.c b/lgc.c
index 486e3fbc..ddf2aa13 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
1/* 1/*
2** $Id: lgc.c,v 1.177 2003/08/27 21:01:44 roberto Exp roberto $ 2** $Id: lgc.c,v 1.178 2003/11/17 19:50:05 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*/
@@ -22,13 +22,6 @@
22#include "ltm.h" 22#include "ltm.h"
23 23
24 24
25typedef struct GCState {
26 GCObject *tmark; /* list of marked objects to be traversed */
27 GCObject *w; /* list of traversed weak tables (to be cleared) */
28 global_State *g;
29} GCState;
30
31
32 25
33#define unblack(x) resetbit((x)->gch.marked, BLACKBIT) 26#define unblack(x) resetbit((x)->gch.marked, BLACKBIT)
34#define isblack(x) testbit((x)->gch.marked, BLACKBIT) 27#define isblack(x) testbit((x)->gch.marked, BLACKBIT)
@@ -46,44 +39,44 @@ typedef struct GCState {
46 39
47 40
48 41
49#define markobject(st,o) { checkconsistency(o); \ 42#define markobject(g,o) { checkconsistency(o); \
50 if (iscollectable(o) && !isblack(gcvalue(o))) reallymarkobject(st,gcvalue(o)); } 43 if (iscollectable(o) && !isblack(gcvalue(o))) reallymarkobject(g,gcvalue(o)); }
51 44
52#define condmarkobject(st,o,c) { checkconsistency(o); \ 45#define condmarkobject(g,o,c) { checkconsistency(o); \
53 if (iscollectable(o) && !isblack(gcvalue(o)) && (c)) \ 46 if (iscollectable(o) && !isblack(gcvalue(o)) && (c)) \
54 reallymarkobject(st,gcvalue(o)); } 47 reallymarkobject(g,gcvalue(o)); }
55 48
56#define markvalue(st,t) { if (!isblack(valtogco(t))) \ 49#define markvalue(g,t) { if (!isblack(valtogco(t))) \
57 reallymarkobject(st, valtogco(t)); } 50 reallymarkobject(g, valtogco(t)); }
58 51
59 52
60 53
61static void reallymarkobject (GCState *st, GCObject *o) { 54static void reallymarkobject (global_State *g, GCObject *o) {
62 lua_assert(!isblack(o)); 55 lua_assert(!isblack(o));
63 blacken(o); 56 blacken(o);
64 switch (o->gch.tt) { 57 switch (o->gch.tt) {
65 case LUA_TUSERDATA: { 58 case LUA_TUSERDATA: {
66 markvalue(st, gcotou(o)->uv.metatable); 59 markvalue(g, gcotou(o)->uv.metatable);
67 break; 60 break;
68 } 61 }
69 case LUA_TFUNCTION: { 62 case LUA_TFUNCTION: {
70 gcotocl(o)->c.gclist = st->tmark; 63 gcotocl(o)->c.gclist = g->gray;
71 st->tmark = o; 64 g->gray = o;
72 break; 65 break;
73 } 66 }
74 case LUA_TTABLE: { 67 case LUA_TTABLE: {
75 gcotoh(o)->gclist = st->tmark; 68 gcotoh(o)->gclist = g->gray;
76 st->tmark = o; 69 g->gray = o;
77 break; 70 break;
78 } 71 }
79 case LUA_TTHREAD: { 72 case LUA_TTHREAD: {
80 gcototh(o)->gclist = st->tmark; 73 gcototh(o)->gclist = g->gray;
81 st->tmark = o; 74 g->gray = o;
82 break; 75 break;
83 } 76 }
84 case LUA_TPROTO: { 77 case LUA_TPROTO: {
85 gcotop(o)->gclist = st->tmark; 78 gcotop(o)->gclist = g->gray;
86 st->tmark = o; 79 g->gray = o;
87 break; 80 break;
88 } 81 }
89 default: lua_assert(o->gch.tt == LUA_TSTRING); 82 default: lua_assert(o->gch.tt == LUA_TSTRING);
@@ -91,11 +84,11 @@ static void reallymarkobject (GCState *st, GCObject *o) {
91} 84}
92 85
93 86
94static void marktmu (GCState *st) { 87static void marktmu (global_State *g) {
95 GCObject *u; 88 GCObject *u;
96 for (u = st->g->tmudata; u; u = u->gch.next) { 89 for (u = g->tmudata; u; u = u->gch.next) {
97 unblack(u); /* may be marked, if left from previous GC */ 90 unblack(u); /* may be marked, if left from previous GC */
98 reallymarkobject(st, u); 91 reallymarkobject(g, u);
99 } 92 }
100} 93}
101 94
@@ -132,14 +125,14 @@ size_t luaC_separateudata (lua_State *L) {
132} 125}
133 126
134 127
135static void traversetable (GCState *st, Table *h) { 128static void traversetable (global_State *g, Table *h) {
136 int i; 129 int i;
137 int weakkey = 0; 130 int weakkey = 0;
138 int weakvalue = 0; 131 int weakvalue = 0;
139 const TObject *mode; 132 const TObject *mode;
140 markvalue(st, h->metatable); 133 markvalue(g, h->metatable);
141 lua_assert(h->lsizenode || h->node == st->g->dummynode); 134 lua_assert(h->lsizenode || h->node == g->dummynode);
142 mode = gfasttm(st->g, h->metatable, TM_MODE); 135 mode = gfasttm(g, h->metatable, TM_MODE);
143 if (mode && ttisstring(mode)) { /* is there a weak mode? */ 136 if (mode && ttisstring(mode)) { /* is there a weak mode? */
144 weakkey = (strchr(svalue(mode), 'k') != NULL); 137 weakkey = (strchr(svalue(mode), 'k') != NULL);
145 weakvalue = (strchr(svalue(mode), 'v') != NULL); 138 weakvalue = (strchr(svalue(mode), 'v') != NULL);
@@ -147,23 +140,23 @@ static void traversetable (GCState *st, Table *h) {
147 h->marked &= ~(KEYWEAK | VALUEWEAK); /* clear bits */ 140 h->marked &= ~(KEYWEAK | VALUEWEAK); /* clear bits */
148 h->marked |= cast(lu_byte, (weakkey << KEYWEAKBIT) | 141 h->marked |= cast(lu_byte, (weakkey << KEYWEAKBIT) |
149 (weakvalue << VALUEWEAKBIT)); 142 (weakvalue << VALUEWEAKBIT));
150 h->gclist = st->w; /* must be cleared after GC, ... */ 143 h->gclist = g->weak; /* must be cleared after GC, ... */
151 st->w = valtogco(h); /* ... so put in the appropriate list */ 144 g->weak = valtogco(h); /* ... so put in the appropriate list */
152 } 145 }
153 } 146 }
154 if (weakkey && weakvalue) return; 147 if (weakkey && weakvalue) return;
155 if (!weakvalue) { 148 if (!weakvalue) {
156 i = h->sizearray; 149 i = h->sizearray;
157 while (i--) 150 while (i--)
158 markobject(st, &h->array[i]); 151 markobject(g, &h->array[i]);
159 } 152 }
160 i = sizenode(h); 153 i = sizenode(h);
161 while (i--) { 154 while (i--) {
162 Node *n = gnode(h, i); 155 Node *n = gnode(h, i);
163 if (!ttisnil(gval(n))) { 156 if (!ttisnil(gval(n))) {
164 lua_assert(!ttisnil(gkey(n))); 157 lua_assert(!ttisnil(gkey(n)));
165 condmarkobject(st, gkey(n), !weakkey); 158 condmarkobject(g, gkey(n), !weakkey);
166 condmarkobject(st, gval(n), !weakvalue); 159 condmarkobject(g, gval(n), !weakvalue);
167 } 160 }
168 } 161 }
169} 162}
@@ -173,7 +166,7 @@ static void traversetable (GCState *st, Table *h) {
173** All marks are conditional because a GC may happen while the 166** All marks are conditional because a GC may happen while the
174** prototype is still being created 167** prototype is still being created
175*/ 168*/
176static void traverseproto (GCState *st, Proto *f) { 169static void traverseproto (global_State *g, Proto *f) {
177 int i; 170 int i;
178 if (f->source) stringmark(f->source); 171 if (f->source) stringmark(f->source);
179 for (i=0; i<f->sizek; i++) { /* mark literal strings */ 172 for (i=0; i<f->sizek; i++) { /* mark literal strings */
@@ -186,7 +179,7 @@ static void traverseproto (GCState *st, Proto *f) {
186 } 179 }
187 for (i=0; i<f->sizep; i++) { /* mark nested protos */ 180 for (i=0; i<f->sizep; i++) { /* mark nested protos */
188 if (f->p[i]) 181 if (f->p[i])
189 markvalue(st, f->p[i]); 182 markvalue(g, f->p[i]);
190 } 183 }
191 for (i=0; i<f->sizelocvars; i++) { /* mark local-variable names */ 184 for (i=0; i<f->sizelocvars; i++) { /* mark local-variable names */
192 if (f->locvars[i].varname) 185 if (f->locvars[i].varname)
@@ -196,22 +189,22 @@ static void traverseproto (GCState *st, Proto *f) {
196 189
197 190
198 191
199static void traverseclosure (GCState *st, Closure *cl) { 192static void traverseclosure (global_State *g, Closure *cl) {
200 if (cl->c.isC) { 193 if (cl->c.isC) {
201 int i; 194 int i;
202 for (i=0; i<cl->c.nupvalues; i++) /* mark its upvalues */ 195 for (i=0; i<cl->c.nupvalues; i++) /* mark its upvalues */
203 markobject(st, &cl->c.upvalue[i]); 196 markobject(g, &cl->c.upvalue[i]);
204 } 197 }
205 else { 198 else {
206 int i; 199 int i;
207 lua_assert(cl->l.nupvalues == cl->l.p->nups); 200 lua_assert(cl->l.nupvalues == cl->l.p->nups);
208 markvalue(st, hvalue(&cl->l.g)); 201 markvalue(g, hvalue(&cl->l.g));
209 markvalue(st, cl->l.p); 202 markvalue(g, cl->l.p);
210 for (i=0; i<cl->l.nupvalues; i++) { /* mark its upvalues */ 203 for (i=0; i<cl->l.nupvalues; i++) { /* mark its upvalues */
211 UpVal *u = cl->l.upvals[i]; 204 UpVal *u = cl->l.upvals[i];
212 if (!isblack(valtogco(u))) { 205 if (!isblack(valtogco(u))) {
213 blacken(valtogco(u)); 206 blacken(valtogco(u));
214 markobject(st, &u->value); 207 markobject(g, &u->value);
215 } 208 }
216 } 209 }
217 } 210 }
@@ -230,48 +223,48 @@ static void checkstacksizes (lua_State *L, StkId max) {
230} 223}
231 224
232 225
233static void traversestack (GCState *st, lua_State *L1) { 226static void traversestack (global_State *g, lua_State *L1) {
234 StkId o, lim; 227 StkId o, lim;
235 CallInfo *ci; 228 CallInfo *ci;
236 markobject(st, gt(L1)); 229 markobject(g, gt(L1));
237 lim = L1->top; 230 lim = L1->top;
238 for (ci = L1->base_ci; ci <= L1->ci; ci++) { 231 for (ci = L1->base_ci; ci <= L1->ci; ci++) {
239 lua_assert(ci->top <= L1->stack_last); 232 lua_assert(ci->top <= L1->stack_last);
240 if (lim < ci->top) lim = ci->top; 233 if (lim < ci->top) lim = ci->top;
241 } 234 }
242 for (o = L1->stack; o < L1->top; o++) 235 for (o = L1->stack; o < L1->top; o++)
243 markobject(st, o); 236 markobject(g, o);
244 for (; o <= lim; o++) 237 for (; o <= lim; o++)
245 setnilvalue(o); 238 setnilvalue(o);
246 checkstacksizes(L1, lim); 239 checkstacksizes(L1, lim);
247} 240}
248 241
249 242
250static void propagatemarks (GCState *st) { 243static void propagatemarks (global_State *g) {
251 while (st->tmark) { /* traverse marked objects */ 244 while (g->gray) { /* traverse marked objects */
252 switch (st->tmark->gch.tt) { 245 switch (g->gray->gch.tt) {
253 case LUA_TTABLE: { 246 case LUA_TTABLE: {
254 Table *h = gcotoh(st->tmark); 247 Table *h = gcotoh(g->gray);
255 st->tmark = h->gclist; 248 g->gray = h->gclist;
256 traversetable(st, h); 249 traversetable(g, h);
257 break; 250 break;
258 } 251 }
259 case LUA_TFUNCTION: { 252 case LUA_TFUNCTION: {
260 Closure *cl = gcotocl(st->tmark); 253 Closure *cl = gcotocl(g->gray);
261 st->tmark = cl->c.gclist; 254 g->gray = cl->c.gclist;
262 traverseclosure(st, cl); 255 traverseclosure(g, cl);
263 break; 256 break;
264 } 257 }
265 case LUA_TTHREAD: { 258 case LUA_TTHREAD: {
266 lua_State *th = gcototh(st->tmark); 259 lua_State *th = gcototh(g->gray);
267 st->tmark = th->gclist; 260 g->gray = th->gclist;
268 traversestack(st, th); 261 traversestack(g, th);
269 break; 262 break;
270 } 263 }
271 case LUA_TPROTO: { 264 case LUA_TPROTO: {
272 Proto *p = gcotop(st->tmark); 265 Proto *p = gcotop(g->gray);
273 st->tmark = p->gclist; 266 g->gray = p->gclist;
274 traverseproto(st, p); 267 traverseproto(g, p);
275 break; 268 break;
276 } 269 }
277 default: lua_assert(0); 270 default: lua_assert(0);
@@ -437,28 +430,26 @@ void luaC_sweep (lua_State *L, int all) {
437 430
438 431
439/* mark root set */ 432/* mark root set */
440static void markroot (GCState *st, lua_State *L) { 433static void markroot (global_State *g, lua_State *L) {
441 global_State *g = st->g; 434 markobject(g, defaultmeta(L));
442 markobject(st, defaultmeta(L)); 435 markobject(g, registry(L));
443 markobject(st, registry(L)); 436 traversestack(g, g->mainthread);
444 traversestack(st, g->mainthread);
445 if (L != g->mainthread) /* another thread is running? */ 437 if (L != g->mainthread) /* another thread is running? */
446 markvalue(st, L); /* cannot collect it */ 438 markvalue(g, L); /* cannot collect it */
447} 439}
448 440
449 441
450static size_t mark (lua_State *L) { 442static size_t mark (lua_State *L) {
451 size_t deadmem; 443 size_t deadmem;
452 GCState st; 444 global_State *g = G(L);
453 st.g = G(L); 445 lua_assert(g->gray == NULL);
454 st.tmark = NULL; 446 g->weak = NULL;
455 st.w = NULL; 447 markroot(g, L);
456 markroot(&st, L); 448 propagatemarks(g); /* mark all reachable objects */
457 propagatemarks(&st); /* mark all reachable objects */
458 deadmem = luaC_separateudata(L); /* separate userdata to be preserved */ 449 deadmem = luaC_separateudata(L); /* separate userdata to be preserved */
459 marktmu(&st); /* mark `preserved' userdata */ 450 marktmu(g); /* mark `preserved' userdata */
460 propagatemarks(&st); /* remark, to propagate `preserveness' */ 451 propagatemarks(g); /* remark, to propagate `preserveness' */
461 cleartable(st.w); /* remove collected objects from weak tables */ 452 cleartable(g->weak); /* remove collected objects from weak tables */
462 return deadmem; 453 return deadmem;
463} 454}
464 455