src/lgc.c

   1 /*
   2 ** $Id: lgc.c,v 1.23 1999/03/04 21:17:26 roberto Exp $
   3 ** Garbage Collector
   4 ** See Copyright Notice in lua.h
   5 */
   6
   7
   8 #include "ldo.h"
   9 #include "lfunc.h"
  10 #include "lgc.h"
  11 #include "lmem.h"
  12 #include "lobject.h"
  13 #include "lstate.h"
  14 #include "lstring.h"
  15 #include "ltable.h"
  16 #include "ltm.h"
  17 #include "lua.h"
  18
  19
  20
  21 static int markobject (TObject *o);
  22
  23
  24
  25 /*
  26 ** =======================================================
  27 ** REF mechanism
  28 ** =======================================================
  29 */
  30
  31
  32 int luaC_ref (TObject *o, int lock) {
  33   int ref;
  34   if (ttype(o) == LUA_T_NIL)
  35     ref = -1;   /* special ref for nil */
  36   else {
  37     for (ref=0; ref<L->refSize; ref++)
  38       if (L->refArray[ref].status == FREE)
  39         break;
  40     if (ref == L->refSize) {  /* no more empty spaces? */
  41       luaM_growvector(L->refArray, L->refSize, 1, struct ref, refEM, MAX_INT);
  42       L->refSize++;
  43     }
  44     L->refArray[ref].o = *o;
  45     L->refArray[ref].status = lock ? LOCK : HOLD;
  46   }
  47   return ref;
  48 }
  49
  50
  51 void lua_unref (int ref)
  52 {
  53   if (ref >= 0 && ref < L->refSize)
  54     L->refArray[ref].status = FREE;
  55 }
  56
  57
  58 TObject* luaC_getref (int ref)
  59 {
  60   if (ref == -1)
  61     return &luaO_nilobject;
  62   if (ref >= 0 && ref < L->refSize &&
  63       (L->refArray[ref].status == LOCK || L->refArray[ref].status == HOLD))
  64     return &L->refArray[ref].o;
  65   else
  66     return NULL;
  67 }
  68
  69
  70 static void travlock (void)
  71 {
  72   int i;
  73   for (i=0; i<L->refSize; i++)
  74     if (L->refArray[i].status == LOCK)
  75       markobject(&L->refArray[i].o);
  76 }
  77
  78
  79 static int ismarked (TObject *o)
  80 {
  81   /* valid only for locked objects */
  82   switch (o->ttype) {
  83     case LUA_T_STRING: case LUA_T_USERDATA:
  84       return o->value.ts->head.marked;
  85     case LUA_T_ARRAY:
  86       return o->value.a->head.marked;
  87     case LUA_T_CLOSURE:
  88       return o->value.cl->head.marked;
  89     case LUA_T_PROTO:
  90       return o->value.tf->head.marked;
  91 #ifdef DEBUG
  92     case LUA_T_LINE: case LUA_T_CLMARK:
  93     case LUA_T_CMARK: case LUA_T_PMARK:
  94       LUA_INTERNALERROR("invalid type");
  95 #endif
  96     default:  /* nil, number or cproto */
  97       return 1;
  98   }
  99 }
 100
 101
 102 static void invalidaterefs (void)
 103 {
 104   int i;
 105   for (i=0; i<L->refSize; i++)
 106     if (L->refArray[i].status == HOLD && !ismarked(&L->refArray[i].o))
 107       L->refArray[i].status = COLLECTED;
 108 }
 109
 110
 111
 112 void luaC_hashcallIM (Hash *l)
 113 {
 114   TObject t;
 115   ttype(&t) = LUA_T_ARRAY;
 116   for (; l; l=(Hash *)l->head.next) {
 117     avalue(&t) = l;
 118     luaD_gcIM(&t);
 119   }
 120 }
 121
 122
 123 void luaC_strcallIM (TaggedString *l)
 124 {
 125   TObject o;
 126   ttype(&o) = LUA_T_USERDATA;
 127   for (; l; l=(TaggedString *)l->head.next)
 128     if (l->constindex == -1) {  /* is userdata? */
 129       tsvalue(&o) = l;
 130       luaD_gcIM(&o);
 131     }
 132 }
 133
 134
 135
 136 static GCnode *listcollect (GCnode *l)
 137 {
 138   GCnode *frees = NULL;
 139   while (l) {
 140     GCnode *next = l->next;
 141     l->marked = 0;
 142     while (next && !next->marked) {
 143       l->next = next->next;
 144       next->next = frees;
 145       frees = next;
 146       next = l->next;
 147     }
 148     l = next;
 149   }
 150   return frees;
 151 }
 152
 153
 154 static void strmark (TaggedString *s)
 155 {
 156   if (!s->head.marked)
 157     s->head.marked = 1;
 158 }
 159
 160
 161 static void protomark (TProtoFunc *f) {
 162   if (!f->head.marked) {
 163     int i;
 164     f->head.marked = 1;
 165     strmark(f->source);
 166     for (i=0; i<f->nconsts; i++)
 167       markobject(&f->consts[i]);
 168   }
 169 }
 170
 171
 172 static void closuremark (Closure *f)
 173 {
 174   if (!f->head.marked) {
 175     int i;
 176     f->head.marked = 1;
 177     for (i=f->nelems; i>=0; i--)
 178       markobject(&f->consts[i]);
 179   }
 180 }
 181
 182
 183 static void hashmark (Hash *h)
 184 {
 185   if (!h->head.marked) {
 186     int i;
 187     h->head.marked = 1;
 188     for (i=0; i<nhash(h); i++) {
 189       Node *n = node(h,i);
 190       if (ttype(ref(n)) != LUA_T_NIL) {
 191         markobject(&n->ref);
 192         markobject(&n->val);
 193       }
 194     }
 195   }
 196 }
 197
 198
 199 static void globalmark (void)
 200 {
 201   TaggedString *g;
 202   for (g=(TaggedString *)L->rootglobal.next; g; g=(TaggedString *)g->head.next){
 203     LUA_ASSERT(g->constindex >= 0, "userdata in global list");
 204     if (g->u.s.globalval.ttype != LUA_T_NIL) {
 205       markobject(&g->u.s.globalval);
 206       strmark(g);  /* cannot collect non nil global variables */
 207     }
 208   }
 209 }
 210
 211
 212 static int markobject (TObject *o)
 213 {
 214   switch (ttype(o)) {
 215     case LUA_T_USERDATA:  case LUA_T_STRING:
 216       strmark(tsvalue(o));
 217       break;
 218     case LUA_T_ARRAY:
 219       hashmark(avalue(o));
 220       break;
 221     case LUA_T_CLOSURE:  case LUA_T_CLMARK:
 222       closuremark(o->value.cl);
 223       break;
 224     case LUA_T_PROTO: case LUA_T_PMARK:
 225       protomark(o->value.tf);
 226       break;
 227     default: break;  /* numbers, cprotos, etc */
 228   }
 229   return 0;
 230 }
 231
 232
 233
 234 static void markall (void)
 235 {
 236   luaD_travstack(markobject); /* mark stack objects */
 237   globalmark();  /* mark global variable values and names */
 238   travlock(); /* mark locked objects */
 239   luaT_travtagmethods(markobject);  /* mark fallbacks */
 240 }
 241
 242
 243 long lua_collectgarbage (long limit)
 244 {
 245   unsigned long recovered = L->nblocks;  /* to subtract nblocks after gc */
 246   Hash *freetable;
 247   TaggedString *freestr;
 248   TProtoFunc *freefunc;
 249   Closure *freeclos;
 250   markall();
 251   invalidaterefs();
 252   freestr = luaS_collector();
 253   freetable = (Hash *)listcollect(&(L->roottable));
 254   freefunc = (TProtoFunc *)listcollect(&(L->rootproto));
 255   freeclos = (Closure *)listcollect(&(L->rootcl));
 256   L->GCthreshold *= 4;  /* to avoid GC during GC */
 257   luaC_hashcallIM(freetable);  /* GC tag methods for tables */
 258   luaC_strcallIM(freestr);  /* GC tag methods for userdata */
 259   luaD_gcIM(&luaO_nilobject);  /* GC tag method for nil (signal end of GC) */
 260   luaH_free(freetable);
 261   luaS_free(freestr);
 262   luaF_freeproto(freefunc);
 263   luaF_freeclosure(freeclos);
 264   recovered = recovered-L->nblocks;
 265   L->GCthreshold = (limit == 0) ? 2*L->nblocks : L->nblocks+limit;
 266   return recovered;
 267 }
 268
 269
 270 void luaC_checkGC (void)
 271 {
 272   if (L->nblocks >= L->GCthreshold)
 273     lua_collectgarbage(0);
 274 }
 275