rpm  4.5
lgc.c
Go to the documentation of this file.
1 /*
2 ** $Id: lgc.c,v 1.2 2004/03/19 21:14:32 niemeyer Exp $
3 ** Garbage Collector
4 ** See Copyright Notice in lua.h
5 */
6 
7 #include <string.h>
8 
9 #define lgc_c
10 
11 #include "lua.h"
12 
13 #include "ldebug.h"
14 #include "ldo.h"
15 #include "lfunc.h"
16 #include "lgc.h"
17 #include "lmem.h"
18 #include "lobject.h"
19 #include "lstate.h"
20 #include "lstring.h"
21 #include "ltable.h"
22 #include "ltm.h"
23 
24 
25 typedef struct GCState {
26 /*@null@*/
27  GCObject *tmark; /* list of marked objects to be traversed */
28 /*@null@*/
29  GCObject *wk; /* list of traversed key-weak tables (to be cleared) */
30 /*@null@*/
31  GCObject *wv; /* list of traversed value-weak tables */
32 /*@null@*/
33  GCObject *wkv; /* list of traversed key-value weak tables */
34 /*@null@*/
36 } GCState;
37 
38 
39 /*
40 ** some userful bit tricks
41 */
42 #define setbit(x,b) ((x) |= (1<<(b)))
43 #define resetbit(x,b) ((x) &= cast(lu_byte, ~(1<<(b))))
44 #define testbit(x,b) ((x) & (1<<(b)))
45 
46 #define unmark(x) resetbit((x)->gch.marked, 0)
47 #define ismarked(x) ((x)->gch.marked & ((1<<4)|1))
48 
49 #define stringmark(s) setbit((s)->tsv.marked, 0)
50 
51 
52 #define isfinalized(u) (!testbit((u)->uv.marked, 1))
53 #define markfinalized(u) resetbit((u)->uv.marked, 1)
54 
55 
56 #define KEYWEAKBIT 1
57 #define VALUEWEAKBIT 2
58 #define KEYWEAK (1<<KEYWEAKBIT)
59 #define VALUEWEAK (1<<VALUEWEAKBIT)
60 
61 
62 
63 #define markobject(st,o) { checkconsistency(o); \
64  if (iscollectable(o) && !ismarked(gcvalue(o))) reallymarkobject(st,gcvalue(o)); }
65 
66 #define condmarkobject(st,o,c) { checkconsistency(o); \
67  if (iscollectable(o) && !ismarked(gcvalue(o)) && (c)) \
68  reallymarkobject(st,gcvalue(o)); }
69 
70 #define markvalue(st,t) { if (!ismarked(valtogco(t))) \
71  reallymarkobject(st, valtogco(t)); }
72 
73 
74 
75 static void reallymarkobject (GCState *st, GCObject *o)
76  /*@modifies st, o @*/
77 {
78  lua_assert(!ismarked(o));
79  setbit(o->gch.marked, 0); /* mark object */
80  switch (o->gch.tt) {
81  case LUA_TUSERDATA: {
82  markvalue(st, gcotou(o)->uv.metatable);
83  break;
84  }
85  case LUA_TFUNCTION: {
86  gcotocl(o)->c.gclist = st->tmark;
87  st->tmark = o;
88  break;
89  }
90  case LUA_TTABLE: {
91  gcotoh(o)->gclist = st->tmark;
92  st->tmark = o;
93  break;
94  }
95  case LUA_TTHREAD: {
96 /*@-onlytrans@*/
97  gcototh(o)->gclist = st->tmark;
98 /*@=onlytrans@*/
99  st->tmark = o;
100  break;
101  }
102  case LUA_TPROTO: {
103  gcotop(o)->gclist = st->tmark;
104  st->tmark = o;
105  break;
106  }
107  default: lua_assert(o->gch.tt == LUA_TSTRING);
108  }
109 }
110 
111 
112 static void marktmu (GCState *st)
113  /*@modifies st @*/
114 {
115  GCObject *u;
116  for (u = st->g->tmudata; u; u = u->gch.next) {
117  unmark(u); /* may be marked, if left from previous GC */
118  reallymarkobject(st, u);
119  }
120 }
121 
122 
123 /* move `dead' udata that need finalization to list `tmudata' */
125  size_t deadmem = 0;
126  GCObject **p = &G(L)->rootudata;
127  GCObject *curr;
128  GCObject *collected = NULL; /* to collect udata with gc event */
129  GCObject **lastcollected = &collected;
130  while ((curr = *p) != NULL) {
131  lua_assert(curr->gch.tt == LUA_TUSERDATA);
132  if (ismarked(curr) || isfinalized(gcotou(curr)))
133  p = &curr->gch.next; /* don't bother with them */
134 
135  else if (fasttm(L, gcotou(curr)->uv.metatable, TM_GC) == NULL) {
136  markfinalized(gcotou(curr)); /* don't need finalization */
137  p = &curr->gch.next;
138  }
139  else { /* must call its gc method */
140  deadmem += sizeudata(gcotou(curr)->uv.len);
141  *p = curr->gch.next;
142  curr->gch.next = NULL; /* link `curr' at the end of `collected' list */
143  *lastcollected = curr;
144  lastcollected = &curr->gch.next;
145  }
146  }
147  /* insert collected udata with gc event into `tmudata' list */
148 /*@-dependenttrans@*/
149  *lastcollected = G(L)->tmudata;
150 /*@=dependenttrans@*/
151  G(L)->tmudata = collected;
152  return deadmem;
153 }
154 
155 
156 static void removekey (Node *n)
157  /*@modifies n @*/
158 {
159  setnilvalue(gval(n)); /* remove corresponding value ... */
160  if (iscollectable(gkey(n)))
161  setttype(gkey(n), LUA_TNONE); /* dead key; remove it */
162 }
163 
164 
165 static void traversetable (GCState *st, Table *h)
166  /*@modifies st, h @*/
167 {
168  int i;
169  int weakkey = 0;
170  int weakvalue = 0;
171  const TObject *mode;
172  markvalue(st, h->metatable);
173  lua_assert(h->lsizenode || h->node == st->g->dummynode);
174  mode = gfasttm(st->g, h->metatable, TM_MODE);
175  if (mode && ttisstring(mode)) { /* is there a weak mode? */
176  weakkey = (strchr(svalue(mode), 'k') != NULL);
177  weakvalue = (strchr(svalue(mode), 'v') != NULL);
178  if (weakkey || weakvalue) { /* is really weak? */
179  GCObject **weaklist;
180  h->marked &= ~(KEYWEAK | VALUEWEAK); /* clear bits */
181  h->marked |= cast(lu_byte, (weakkey << KEYWEAKBIT) |
182  (weakvalue << VALUEWEAKBIT));
183  weaklist = (weakkey && weakvalue) ? &st->wkv :
184  (weakkey) ? &st->wk :
185  &st->wv;
186  h->gclist = *weaklist; /* must be cleared after GC, ... */
187  *weaklist = valtogco(h); /* ... so put in the appropriate list */
188  }
189  }
190  if (!weakvalue) {
191  i = h->sizearray;
192  while (i--)
193  markobject(st, &h->array[i]);
194  }
195  i = sizenode(h);
196  while (i--) {
197  Node *n = gnode(h, i);
198  if (!ttisnil(gval(n))) {
199  lua_assert(!ttisnil(gkey(n)));
200  condmarkobject(st, gkey(n), !weakkey);
201  condmarkobject(st, gval(n), !weakvalue);
202  }
203  }
204 }
205 
206 
207 static void traverseproto (GCState *st, Proto *f)
208  /*@modifies st, f @*/
209 {
210  int i;
211  stringmark(f->source);
212  for (i=0; i<f->sizek; i++) { /* mark literal strings */
213  if (ttisstring(f->k+i))
214  stringmark(tsvalue(f->k+i));
215  }
216  for (i=0; i<f->sizeupvalues; i++) /* mark upvalue names */
217  stringmark(f->upvalues[i]);
218  for (i=0; i<f->sizep; i++) /* mark nested protos */
219  markvalue(st, f->p[i]);
220  for (i=0; i<f->sizelocvars; i++) /* mark local-variable names */
221  stringmark(f->locvars[i].varname);
223 }
224 
225 
226 
227 static void traverseclosure (GCState *st, Closure *cl)
228  /*@modifies st, cl @*/
229 {
230  if (cl->c.isC) {
231  int i;
232  for (i=0; i<cl->c.nupvalues; i++) /* mark its upvalues */
233  markobject(st, &cl->c.upvalue[i]);
234  }
235  else {
236  int i;
237  lua_assert(cl->l.nupvalues == cl->l.p->nups);
238  markvalue(st, hvalue(&cl->l.g));
239  markvalue(st, cl->l.p);
240  for (i=0; i<cl->l.nupvalues; i++) { /* mark its upvalues */
241  UpVal *u = cl->l.upvals[i];
242  if (!u->marked) {
243  markobject(st, &u->value);
244  u->marked = 1;
245  }
246  }
247  }
248 }
249 
250 
251 static void checkstacksizes (lua_State *L, StkId max)
252  /*@modifies L @*/
253 {
254  int used = L->ci - L->base_ci; /* number of `ci' in use */
255  if (4*used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci)
256  luaD_reallocCI(L, L->size_ci/2); /* still big enough... */
258  used = max - L->stack; /* part of stack in use */
259  if (4*used < L->stacksize && 2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize)
260  luaD_reallocstack(L, L->stacksize/2); /* still big enough... */
262 }
263 
264 
265 static void traversestack (GCState *st, lua_State *L1)
266  /*@modifies st, L1 @*/
267 {
268  StkId o, lim;
269  CallInfo *ci;
270  markobject(st, gt(L1));
271  lim = L1->top;
272  for (ci = L1->base_ci; ci <= L1->ci; ci++) {
273  lua_assert(ci->top <= L1->stack_last);
275  if (lim < ci->top)
276  lim = ci->top;
277  }
278  for (o = L1->stack; o < L1->top; o++)
279  markobject(st, o);
280  for (; o <= lim; o++)
281  setnilvalue(o);
282  checkstacksizes(L1, lim);
283 }
284 
285 
286 static void propagatemarks (GCState *st)
287  /*@modifies st @*/
288 {
289  while (st->tmark) { /* traverse marked objects */
290  switch (st->tmark->gch.tt) {
291  case LUA_TTABLE: {
292  Table *h = gcotoh(st->tmark);
293  st->tmark = h->gclist;
294  traversetable(st, h);
295  break;
296  }
297  case LUA_TFUNCTION: {
298  Closure *cl = gcotocl(st->tmark);
299  st->tmark = cl->c.gclist;
300  traverseclosure(st, cl);
301  break;
302  }
303  case LUA_TTHREAD: {
304  lua_State *th = gcototh(st->tmark);
305 /*@-dependenttrans@*/
306  st->tmark = th->gclist;
307 /*@=dependenttrans@*/
308  traversestack(st, th);
309  break;
310  }
311  case LUA_TPROTO: {
312  Proto *p = gcotop(st->tmark);
313  st->tmark = p->gclist;
314  traverseproto(st, p);
315  break;
316  }
317  default: lua_assert(0);
318  }
319  }
320 }
321 
322 
323 static int valismarked (const TObject *o)
324  /*@modifies o @*/
325 {
326  if (ttisstring(o))
327  stringmark(tsvalue(o)); /* strings are `values', so are never weak */
328  return !iscollectable(o) || testbit(o->value.gc->gch.marked, 0);
329 }
330 
331 
332 /*
333 ** clear collected keys from weaktables
334 */
335 static void cleartablekeys (/*@null@*/ GCObject *l)
336  /*@modifies l @*/
337 {
338  while (l) {
339  Table *h = gcotoh(l);
340  int i = sizenode(h);
341  lua_assert(h->marked & KEYWEAK);
342  while (i--) {
343  Node *n = gnode(h, i);
344  if (!valismarked(gkey(n))) /* key was collected? */
345  removekey(n); /* remove entry from table */
346  }
347  l = h->gclist;
348  }
349 }
350 
351 
352 /*
353 ** clear collected values from weaktables
354 */
355 static void cleartablevalues (/*@null@*/ GCObject *l)
356  /*@modifies l @*/
357 {
358  while (l) {
359  Table *h = gcotoh(l);
360  int i = h->sizearray;
362  while (i--) {
363  TObject *o = &h->array[i];
364  if (!valismarked(o)) /* value was collected? */
365  setnilvalue(o); /* remove value */
366  }
367  i = sizenode(h);
368  while (i--) {
369  Node *n = gnode(h, i);
370  if (!valismarked(gval(n))) /* value was collected? */
371  removekey(n); /* remove entry from table */
372  }
373  l = h->gclist;
374  }
375 }
376 
377 
378 static void freeobj (lua_State *L, GCObject *o)
379  /*@modifies L, o @*/
380 {
381  switch (o->gch.tt) {
382  case LUA_TPROTO: luaF_freeproto(L, gcotop(o)); break;
383  case LUA_TFUNCTION: luaF_freeclosure(L, gcotocl(o)); break;
384  case LUA_TUPVAL: luaM_freelem(L, gcotouv(o)); break;
385  case LUA_TTABLE: luaH_free(L, gcotoh(o)); break;
386  case LUA_TTHREAD: {
387  lua_assert(gcototh(o) != L && gcototh(o) != G(L)->mainthread);
388  luaE_freethread(L, gcototh(o));
389  break;
390  }
391  case LUA_TSTRING: {
392  luaM_free(L, o, sizestring(gcotots(o)->tsv.len));
393  break;
394  }
395  case LUA_TUSERDATA: {
396  luaM_free(L, o, sizeudata(gcotou(o)->uv.len));
397  break;
398  }
399  default: lua_assert(0);
400  }
401 }
402 
403 
404 static int sweeplist (lua_State *L, GCObject **p, int limit)
405  /*@modifies L, *p @*/
406 {
407  GCObject *curr;
408  int count = 0; /* number of collected items */
409  while ((curr = *p) != NULL) {
410  if (curr->gch.marked > limit) {
411  unmark(curr);
412  p = &curr->gch.next;
413  }
414  else {
415  count++;
416 /*@-dependenttrans@*/
417  *p = curr->gch.next;
418 /*@=dependenttrans@*/
419  freeobj(L, curr);
420  }
421  }
422  return count;
423 }
424 
425 
426 static void sweepstrings (lua_State *L, int all)
427  /*@modifies L @*/
428 {
429  int i;
430  for (i=0; i<G(L)->strt.size; i++) { /* for each list */
431  G(L)->strt.nuse -= sweeplist(L, &G(L)->strt.hash[i], all);
432  }
433 }
434 
435 
436 static void checkSizes (lua_State *L, size_t deadmem)
437  /*@modifies L @*/
438 {
439  /* check size of string hash */
440  if (G(L)->strt.nuse < cast(ls_nstr, G(L)->strt.size/4) &&
441  G(L)->strt.size > MINSTRTABSIZE*2)
442  luaS_resize(L, G(L)->strt.size/2); /* table is too big */
443  /* check size of buffer */
444  if (luaZ_sizebuffer(&G(L)->buff) > LUA_MINBUFFER*2) { /* buffer too big? */
445  size_t newsize = luaZ_sizebuffer(&G(L)->buff) / 2;
446  luaZ_resizebuffer(L, &G(L)->buff, newsize);
447  }
448  G(L)->GCthreshold = 2*G(L)->nblocks - deadmem; /* new threshold */
449 }
450 
451 
452 static void do1gcTM (lua_State *L, Udata *udata)
453  /*@modifies L, udata @*/
454 {
455  const TObject *tm = fasttm(L, udata->uv.metatable, TM_GC);
456  if (tm != NULL) {
457  setobj2s(L->top, tm);
458  setuvalue(L->top+1, udata);
459  L->top += 2;
460  luaD_call(L, L->top - 2, 0);
461  }
462 }
463 
464 
466  lu_byte oldah = L->allowhook;
467  L->allowhook = 0; /* stop debug hooks during GC tag methods */
468  L->top++; /* reserve space to keep udata while runs its gc method */
469  while (G(L)->tmudata != NULL) {
470  GCObject *o = G(L)->tmudata;
471  Udata *udata = gcotou(o);
472  G(L)->tmudata = udata->uv.next; /* remove udata from `tmudata' */
473  udata->uv.next = G(L)->rootudata; /* return it to `root' list */
474  G(L)->rootudata = o;
475  setuvalue(L->top - 1, udata); /* keep a reference to it */
476  unmark(o);
477  markfinalized(udata);
478  do1gcTM(L, udata);
479  }
480  L->top--;
481  L->allowhook = oldah; /* restore hooks */
482 }
483 
484 
485 void luaC_sweep (lua_State *L, int all) {
486  if (all) all = 256; /* larger than any mark */
487  sweeplist(L, &G(L)->rootudata, all);
488  sweepstrings(L, all);
489  sweeplist(L, &G(L)->rootgc, all);
490 }
491 
492 
493 /* mark root set */
494 static void markroot (GCState *st, lua_State *L)
495  /*@modifies st, L @*/
496 {
497  global_State *g = st->g;
498  markobject(st, defaultmeta(L));
499  markobject(st, registry(L));
500  traversestack(st, g->mainthread);
501  if (L != g->mainthread) /* another thread is running? */
502  markvalue(st, L); /* cannot collect it */
503 }
504 
505 
506 static size_t mark (lua_State *L)
507  /*@modifies L @*/
508 {
509  size_t deadmem;
510  GCState st;
511  GCObject *wkv;
512  st.g = G(L);
513  st.tmark = NULL;
514  st.wkv = st.wk = st.wv = NULL;
515  markroot(&st, L);
516  propagatemarks(&st); /* mark all reachable objects */
517  cleartablevalues(st.wkv);
518  cleartablevalues(st.wv);
519  wkv = st.wkv; /* keys must be cleared after preserving udata */
520  st.wkv = NULL;
521  st.wv = NULL;
522  deadmem = luaC_separateudata(L); /* separate userdata to be preserved */
523  marktmu(&st); /* mark `preserved' userdata */
524  propagatemarks(&st); /* remark, to propagate `preserveness' */
525  cleartablekeys(wkv);
526  /* `propagatemarks' may resuscitate some weak tables; clear them too */
527  cleartablekeys(st.wk);
528  cleartablevalues(st.wv);
529  cleartablekeys(st.wkv);
530  cleartablevalues(st.wkv);
531  return deadmem;
532 }
533 
534 
536  size_t deadmem = mark(L);
537  luaC_sweep(L, 0);
538  checkSizes(L, deadmem);
539  luaC_callGCTM(L);
540 }
541 
542 
543 void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
544  o->gch.next = G(L)->rootgc;
545  G(L)->rootgc = o;
546  o->gch.marked = 0;
547  o->gch.tt = tt;
548 }
549