src/lgc.c

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