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