diff options
Diffstat (limited to 'lgc.c')
-rw-r--r-- | lgc.c | 143 |
1 files changed, 67 insertions, 76 deletions
@@ -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 | ||
25 | typedef 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 | ||
61 | static void reallymarkobject (GCState *st, GCObject *o) { | 54 | static 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 | ||
94 | static void marktmu (GCState *st) { | 87 | static 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 | ||
135 | static void traversetable (GCState *st, Table *h) { | 128 | static 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 | */ |
176 | static void traverseproto (GCState *st, Proto *f) { | 169 | static 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 | ||
199 | static void traverseclosure (GCState *st, Closure *cl) { | 192 | static 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 | ||
233 | static void traversestack (GCState *st, lua_State *L1) { | 226 | static 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 | ||
250 | static void propagatemarks (GCState *st) { | 243 | static 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 */ |
440 | static void markroot (GCState *st, lua_State *L) { | 433 | static 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 | ||
450 | static size_t mark (lua_State *L) { | 442 | static 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 | ||