1 /*
2 ** $Id: lgc.c,v 1.2 2002/07/12 07:49:04 jcatki Exp $
3 ** Garbage Collector
4 ** See Copyright Notice in lua.h
5 */
6
7 #include "lua.h"
8
9 #include "ldo.h"
10 #include "lfunc.h"
11 #include "lgc.h"
12 #include "lmem.h"
13 #include "lobject.h"
14 #include "lstate.h"
15 #include "lstring.h"
16 #include "ltable.h"
17 #include "ltm.h"
18
19
20 typedef struct GCState {
21 Hash *tmark; /* list of marked tables to be visited */
22 Closure *cmark; /* list of marked closures to be visited */
23 } GCState;
24
25
26
27 static void markobject (GCState *st, TObject *o);
28
29
30 /* mark a string; marks larger than 1 cannot be changed */
31 #define strmark(s) {if ((s)->marked == 0) (s)->marked = 1;}
32
33
34
protomark(Proto * f)35 static void protomark (Proto *f) {
36 if (!f->marked) {
37 int i;
38 f->marked = 1;
39 strmark(f->source);
40 for (i=0; i<f->nkstr; i++)
41 strmark(f->kstr[i]);
42 for (i=0; i<f->nkproto; i++)
43 protomark(f->kproto[i]);
44 for (i=0; i<f->nlocvars; i++) /* mark local-variable names */
45 strmark(f->locvars[i].varname);
46 }
47 }
48
49
markstack(lua_State * L,GCState * st)50 static void markstack (lua_State *L, GCState *st) {
51 StkId o;
52 for (o=L->stack; o<L->top; o++)
53 markobject(st, o);
54 }
55
56
marklock(lua_State * L,GCState * st)57 static void marklock (lua_State *L, GCState *st) {
58 int i;
59 for (i=0; i<L->refSize; i++) {
60 if (L->refArray[i].st == LOCK)
61 markobject(st, &L->refArray[i].o);
62 }
63 }
64
65
markclosure(GCState * st,Closure * cl)66 static void markclosure (GCState *st, Closure *cl) {
67 if (!ismarked(cl)) {
68 if (!cl->isC)
69 protomark(cl->f.l);
70 cl->mark = st->cmark; /* chain it for later traversal */
71 st->cmark = cl;
72 }
73 }
74
75
marktagmethods(lua_State * L,GCState * st)76 static void marktagmethods (lua_State *L, GCState *st) {
77 int e;
78 for (e=0; e<TM_N; e++) {
79 int t;
80 for (t=0; t<=L->last_tag; t++) {
81 Closure *cl = luaT_gettm(L, t, e);
82 if (cl) markclosure(st, cl);
83 }
84 }
85 }
86
87
markobject(GCState * st,TObject * o)88 static void markobject (GCState *st, TObject *o) {
89 switch (ttype(o)) {
90 case LUA_TUSERDATA: case LUA_TSTRING:
91 strmark(tsvalue(o));
92 break;
93 case LUA_TMARK:
94 markclosure(st, infovalue(o)->func);
95 break;
96 case LUA_TFUNCTION:
97 markclosure(st, clvalue(o));
98 break;
99 case LUA_TTABLE: {
100 if (!ismarked(hvalue(o))) {
101 hvalue(o)->mark = st->tmark; /* chain it in list of marked */
102 st->tmark = hvalue(o);
103 }
104 break;
105 }
106 default: break; /* numbers, etc */
107 }
108 }
109
110
markall(lua_State * L)111 static void markall (lua_State *L) {
112 GCState st;
113 st.cmark = NULL;
114 st.tmark = L->gt; /* put table of globals in mark list */
115 L->gt->mark = NULL;
116 marktagmethods(L, &st); /* mark tag methods */
117 markstack(L, &st); /* mark stack objects */
118 marklock(L, &st); /* mark locked objects */
119 for (;;) { /* mark tables and closures */
120 if (st.cmark) {
121 int i;
122 Closure *f = st.cmark; /* get first closure from list */
123 st.cmark = f->mark; /* remove it from list */
124 for (i=0; i<f->nupvalues; i++) /* mark its upvalues */
125 markobject(&st, &f->upvalue[i]);
126 }
127 else if (st.tmark) {
128 int i;
129 Hash *h = st.tmark; /* get first table from list */
130 st.tmark = h->mark; /* remove it from list */
131 for (i=0; i<h->size; i++) {
132 Node *n = node(h, i);
133 if (ttype(key(n)) != LUA_TNIL) {
134 if (ttype(val(n)) == LUA_TNIL)
135 luaH_remove(h, key(n)); /* dead element; try to remove it */
136 markobject(&st, &n->key);
137 markobject(&st, &n->val);
138 }
139 }
140 }
141 else break; /* nothing else to mark */
142 }
143 }
144
145
hasmark(const TObject * o)146 static int hasmark (const TObject *o) {
147 /* valid only for locked objects */
148 switch (o->ttype) {
149 case LUA_TSTRING: case LUA_TUSERDATA:
150 return tsvalue(o)->marked;
151 case LUA_TTABLE:
152 return ismarked(hvalue(o));
153 case LUA_TFUNCTION:
154 return ismarked(clvalue(o));
155 default: /* number */
156 return 1;
157 }
158 }
159
160
161 /* macro for internal debugging; check if a link of free refs is valid */
162 #define VALIDLINK(L, st,n) (NONEXT <= (st) && (st) < (n))
163
invalidaterefs(lua_State * L)164 static void invalidaterefs (lua_State *L) {
165 int n = L->refSize;
166 int i;
167 for (i=0; i<n; i++) {
168 struct Ref *r = &L->refArray[i];
169 if (r->st == HOLD && !hasmark(&r->o))
170 r->st = COLLECTED;
171 LUA_ASSERT((r->st == LOCK && hasmark(&r->o)) ||
172 (r->st == HOLD && hasmark(&r->o)) ||
173 r->st == COLLECTED ||
174 r->st == NONEXT ||
175 (r->st < n && VALIDLINK(L, L->refArray[r->st].st, n)),
176 "inconsistent ref table");
177 }
178 LUA_ASSERT(VALIDLINK(L, L->refFree, n), "inconsistent ref table");
179 }
180
181
182
collectproto(lua_State * L)183 static void collectproto (lua_State *L) {
184 Proto **p = &L->rootproto;
185 Proto *next;
186 while ((next = *p) != NULL) {
187 if (next->marked) {
188 next->marked = 0;
189 p = &next->next;
190 }
191 else {
192 *p = next->next;
193 luaF_freeproto(L, next);
194 }
195 }
196 }
197
198
collectclosure(lua_State * L)199 static void collectclosure (lua_State *L) {
200 Closure **p = &L->rootcl;
201 Closure *next;
202 while ((next = *p) != NULL) {
203 if (ismarked(next)) {
204 next->mark = next; /* unmark */
205 p = &next->next;
206 }
207 else {
208 *p = next->next;
209 luaF_freeclosure(L, next);
210 }
211 }
212 }
213
214
collecttable(lua_State * L)215 static void collecttable (lua_State *L) {
216 Hash **p = &L->roottable;
217 Hash *next;
218 while ((next = *p) != NULL) {
219 if (ismarked(next)) {
220 next->mark = next; /* unmark */
221 p = &next->next;
222 }
223 else {
224 *p = next->next;
225 luaH_free(L, next);
226 }
227 }
228 }
229
230
checktab(lua_State * L,stringtable * tb)231 static void checktab (lua_State *L, stringtable *tb) {
232 if (tb->nuse < (lint32)(tb->size/4) && tb->size > 10)
233 luaS_resize(L, tb, tb->size/2); /* table is too big */
234 }
235
236
collectstrings(lua_State * L,int all)237 static void collectstrings (lua_State *L, int all) {
238 int i;
239 for (i=0; i<L->strt.size; i++) { /* for each list */
240 TString **p = &L->strt.hash[i];
241 TString *next;
242 while ((next = *p) != NULL) {
243 if (next->marked && !all) { /* preserve? */
244 if (next->marked < FIXMARK) /* does not change FIXMARKs */
245 next->marked = 0;
246 p = &next->nexthash;
247 }
248 else { /* collect */
249 *p = next->nexthash;
250 L->strt.nuse--;
251 L->nblocks -= sizestring(next->len);
252 luaM_free(L, next);
253 }
254 }
255 }
256 checktab(L, &L->strt);
257 }
258
259
collectudata(lua_State * L,int all)260 static void collectudata (lua_State *L, int all) {
261 int i;
262 for (i=0; i<L->udt.size; i++) { /* for each list */
263 TString **p = &L->udt.hash[i];
264 TString *next;
265 while ((next = *p) != NULL) {
266 LUA_ASSERT(next->marked <= 1, "udata cannot be fixed");
267 if (next->marked && !all) { /* preserve? */
268 next->marked = 0;
269 p = &next->nexthash;
270 }
271 else { /* collect */
272 int tag = next->u.d.tag;
273 *p = next->nexthash;
274 next->nexthash = L->TMtable[tag].collected; /* chain udata */
275 L->TMtable[tag].collected = next;
276 L->nblocks -= sizestring(next->len);
277 L->udt.nuse--;
278 }
279 }
280 }
281 checktab(L, &L->udt);
282 }
283
284
285 #define MINBUFFER 256
checkMbuffer(lua_State * L)286 static void checkMbuffer (lua_State *L) {
287 if (L->Mbuffsize > MINBUFFER*2) { /* is buffer too big? */
288 size_t newsize = L->Mbuffsize/2; /* still larger than MINBUFFER */
289 L->nblocks += (newsize - L->Mbuffsize)*sizeof(char);
290 L->Mbuffsize = newsize;
291 luaM_reallocvector(L, L->Mbuffer, newsize, char);
292 }
293 }
294
295
callgcTM(lua_State * L,const TObject * o)296 static void callgcTM (lua_State *L, const TObject *o) {
297 Closure *tm = luaT_gettmbyObj(L, o, TM_GC);
298 if (tm != NULL) {
299 int oldah = L->allowhooks;
300 L->allowhooks = 0; /* stop debug hooks during GC tag methods */
301 luaD_checkstack(L, 2);
302 clvalue(L->top) = tm;
303 ttype(L->top) = LUA_TFUNCTION;
304 *(L->top+1) = *o;
305 L->top += 2;
306 luaD_call(L, L->top-2, 0);
307 L->allowhooks = oldah; /* restore hooks */
308 }
309 }
310
311
callgcTMudata(lua_State * L)312 static void callgcTMudata (lua_State *L) {
313 int tag;
314 TObject o;
315 ttype(&o) = LUA_TUSERDATA;
316 L->GCthreshold = 2*L->nblocks; /* avoid GC during tag methods */
317 for (tag=L->last_tag; tag>=0; tag--) { /* for each tag (in reverse order) */
318 TString *udata;
319 while ((udata = L->TMtable[tag].collected) != NULL) {
320 L->TMtable[tag].collected = udata->nexthash; /* remove it from list */
321 tsvalue(&o) = udata;
322 callgcTM(L, &o);
323 luaM_free(L, udata);
324 }
325 }
326 }
327
328
luaC_collect(lua_State * L,int all)329 void luaC_collect (lua_State *L, int all) {
330 collectudata(L, all);
331 callgcTMudata(L);
332 collectstrings(L, all);
333 collecttable(L);
334 collectproto(L);
335 collectclosure(L);
336 }
337
338
luaC_collectgarbage(lua_State * L)339 void luaC_collectgarbage (lua_State *L) {
340 markall(L);
341 invalidaterefs(L); /* check unlocked references */
342 luaC_collect(L, 0);
343 checkMbuffer(L);
344 L->GCthreshold = 2*L->nblocks; /* set new threshold */
345 callgcTM(L, &luaO_nilobject);
346 }
347
348
luaC_checkGC(lua_State * L)349 void luaC_checkGC (lua_State *L) {
350 if (L->nblocks >= L->GCthreshold)
351 luaC_collectgarbage(L);
352 }
353
354