cleaner way to remark open upvalues

8 files changed, 74 insertions, 63 deletions

diff --git a/lfunc.c b/lfunc.c
index 8513ce22..3171c5ec 100644
--- a/lfunc.c
+++ b/lfunc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lfunc.c,v 2.4 2004/04/30 20:13:38 roberto Exp roberto $
+** $Id: lfunc.c,v 2.5 2004/11/24 19:20:21 roberto Exp $
 ** Auxiliary functions to manipulate prototypes and closures
 ** See Copyright Notice in lua.h
 */
@@ -43,42 +43,66 @@ Closure *luaF_newLclosure (lua_State *L, int nelems, TValue *e) {
 UpVal *luaF_newupval (lua_State *L) {
   UpVal *uv = luaM_new(L, UpVal);
   luaC_link(L, obj2gco(uv), LUA_TUPVAL);
-  uv->v = &uv->value;
+  uv->v = &uv->u.value;
   setnilvalue(uv->v);
   return uv;
 }
 
 
 UpVal *luaF_findupval (lua_State *L, StkId level) {
+  global_State *g = G(L);
   GCObject **pp = &L->openupval;
   UpVal *p;
   UpVal *uv;
   while ((p = ngcotouv(*pp)) != NULL && p->v >= level) {
+    lua_assert(p->v != &p->u.value);
     if (p->v == level) return p;
     pp = &p->next;
   }
   uv = luaM_new(L, UpVal);  /* not found: create a new one */
   uv->tt = LUA_TUPVAL;
-  uv->marked = luaC_white(G(L));
+  uv->marked = luaC_white(g);
   uv->v = level;  /* current value lives in the stack */
   uv->next = *pp;  /* chain it in the proper position */
   *pp = obj2gco(uv);
+  lua_assert(g->uvhead.u.l.next->u.l.prev == &g->uvhead &&
+             g->uvhead.u.l.prev->u.l.next == &g->uvhead);
+  uv->u.l.prev = &g->uvhead;  /* double link it in `uvhead' list */
+  uv->u.l.next = g->uvhead.u.l.next;
+  uv->u.l.next->u.l.prev = uv;
+  g->uvhead.u.l.next = uv;
+  lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
   return uv;
 }
 
 
+static void unlinkupval (UpVal *uv) {
+  lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
+  uv->u.l.next->u.l.prev = uv->u.l.prev;  /* remove from `uvhead' list */
+  uv->u.l.prev->u.l.next = uv->u.l.next;
+}
+
+
+void luaF_freeupval (lua_State *L, UpVal *uv) {
+  if (uv->v != &uv->u.value)  /* is it open? */
+    unlinkupval(uv);  /* remove from open list */
+  luaM_free(L, uv);  /* free upvalue */
+}
+
+
 void luaF_close (lua_State *L, StkId level) {
   UpVal *uv;
   global_State *g = G(L);
   while ((uv = ngcotouv(L->openupval)) != NULL && uv->v >= level) {
     GCObject *o = obj2gco(uv);
-    lua_assert(!isblack(o));
+    lua_assert(!isblack(o) && uv->v != &uv->u.value);
     L->openupval = uv->next;  /* remove from `open' list */
     if (isdead(g, o))
-      luaM_free(L, uv);  /* free upvalue */
+      luaF_freeupval(L, uv);  /* free upvalue */
     else {
-      setobj(L, &uv->value, uv->v);
-      uv->v = &uv->value;  /* now current value lives here */
+      unlinkupval(uv);
+      setobj(L, &uv->u.value, uv->v);
+      uv->v = &uv->u.value;  /* now current value lives here */
       luaC_linkupval(L, uv);  /* link upvalue into `gcroot' list */
     }
   }
diff --git a/lfunc.h b/lfunc.h
index c6e35586..fb542716 100644
--- a/lfunc.h
+++ b/lfunc.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lfunc.h,v 1.23 2003/11/24 18:50:36 roberto Exp roberto $
+** $Id: lfunc.h,v 2.1 2003/12/10 12:13:36 roberto Exp $
 ** Auxiliary functions to manipulate prototypes and closures
 ** See Copyright Notice in lua.h
 */
@@ -26,6 +26,7 @@ UpVal *luaF_findupval (lua_State *L, StkId level);
 void luaF_close (lua_State *L, StkId level);
 void luaF_freeproto (lua_State *L, Proto *f);
 void luaF_freeclosure (lua_State *L, Closure *c);
+void luaF_freeupval (lua_State *L, UpVal *uv);
 
 const char *luaF_getlocalname (const Proto *func, int local_number, int pc);
 
diff --git a/lgc.c b/lgc.c
index af16e882..d40b174c 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 2.20 2005/01/05 18:20:51 roberto Exp roberto $
+** $Id: lgc.c,v 2.21 2005/01/14 14:19:42 roberto Exp $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -83,10 +83,9 @@ static void reallymarkobject (global_State *g, GCObject *o) {
     }
     case LUA_TUPVAL: {
       UpVal *uv = gco2uv(o);
-      if (uv->v == &uv->value) {  /* closed? */
-        markvalue(g, uv->v);
-        gray2black(o);
-      }
+      markvalue(g, uv->v);
+      if (uv->v == &uv->u.value)  /* closed? */
+        gray2black(o);  /* open upvalues are never black */
       return;
     }
     case LUA_TFUNCTION: {
@@ -126,11 +125,11 @@ static void marktmu (global_State *g) {
 /* move `dead' udata that need finalization to list `tmudata' */
 size_t luaC_separateudata (lua_State *L, int all) {
   size_t deadmem = 0;
-  GCObject **p = &G(L)->firstudata;
+  GCObject **p = &G(L)->mainthread->next;
   GCObject *curr;
   GCObject *collected = NULL;  /* to collect udata with gc event */
   GCObject **lastcollected = &collected;
-  while ((curr = *p)->gch.tt == LUA_TUSERDATA) {
+  while ((curr = *p) != NULL) {
     if (!(iswhite(curr) || all) || isfinalized(gco2u(curr)))
       p = &curr->gch.next;  /* don't bother with them */
     else if (fasttm(L, gco2u(curr)->metatable, TM_GC) == NULL) {
@@ -146,7 +145,6 @@ size_t luaC_separateudata (lua_State *L, int all) {
       lastcollected = &curr->gch.next;
     }
   }
-  lua_assert(curr == obj2gco(G(L)->mainthread));
   /* insert collected udata with gc event into `tmudata' list */
   *lastcollected = G(L)->tmudata;
   G(L)->tmudata = collected;
@@ -380,7 +378,7 @@ static void freeobj (lua_State *L, GCObject *o) {
   switch (o->gch.tt) {
     case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break;
     case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(o)); break;
-    case LUA_TUPVAL: luaM_free(L, gco2uv(o)); break;
+    case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break;
     case LUA_TTABLE: luaH_free(L, gco2h(o)); break;
     case LUA_TTHREAD: {
       lua_assert(gco2th(o) != L && gco2th(o) != G(L)->mainthread);
@@ -461,8 +459,8 @@ static void GCTM (lua_State *L) {
   Udata *udata = rawgco2u(o);
   const TValue *tm;
   g->tmudata = udata->uv.next;  /* remove udata from `tmudata' */
-  udata->uv.next = g->firstudata->uv.next;  /* return it to `root' list */
-  g->firstudata->uv.next = o;
+  udata->uv.next = g->mainthread->next;  /* return it to `root' list */
+  g->mainthread->next = o;
   makewhite(g, o);
   tm = fasttm(L, udata->uv.metatable, TM_GC);
   if (tm != NULL) {
@@ -510,18 +508,11 @@ static void markroot (lua_State *L) {
 
 
 static void remarkupvals (global_State *g) {
-  GCObject *o;
-  for (o = obj2gco(g->mainthread); o; o = o->gch.next) {
-    lua_assert(!isblack(o));
-    if (iswhite(o)) {
-      GCObject *curr;
-      for (curr = gco2th(o)->openupval; curr != NULL; curr = curr->gch.next) {
-        if (isgray(curr)) {
-          UpVal *uv = gco2uv(curr);
-          markvalue(g, uv->v);
-        }
-      }
-    }
+  UpVal *uv;
+  for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {
+    lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
+    if (isgray(obj2gco(uv)))
+      markvalue(g, uv->v);
   }
 }
 
diff --git a/lobject.h b/lobject.h
index 2c0a5d26..0c781ef3 100644
--- a/lobject.h
+++ b/lobject.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lobject.h,v 2.8 2004/12/04 18:10:22 roberto Exp roberto $
+** $Id: lobject.h,v 2.9 2005/01/05 18:20:51 roberto Exp $
 ** Type definitions for Lua objects
 ** See Copyright Notice in lua.h
 */
@@ -271,7 +271,13 @@ typedef struct LocVar {
 typedef struct UpVal {
   CommonHeader;
   TValue *v;  /* points to stack or to its own value */
-  TValue value;  /* the value (when closed) */
+  union {
+    TValue value;  /* the value (when closed) */
+    struct {  /* double linked list (when open) */
+      struct UpVal *prev;
+      struct UpVal *next;
+    } l;
+  } u;
 } UpVal;
 
 
diff --git a/lstate.c b/lstate.c
index 33a5cd7d..7596a55d 100644
--- a/lstate.c
+++ b/lstate.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.c,v 2.21 2005/01/05 18:20:51 roberto Exp roberto $
+** $Id: lstate.c,v 2.22 2005/01/14 14:19:42 roberto Exp $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -76,16 +76,8 @@ static void freestack (lua_State *L, lua_State *L1) {
 ** open parts that may cause memory-allocation errors
 */
 static void f_luaopen (lua_State *L, void *ud) {
-  Udata *u;  /* head of udata list */
   global_State *g = G(L);
   UNUSED(ud);
-  u = luaM_new(L, Udata);
-  u->uv.len = 0;
-  u->uv.metatable = NULL;
-  g->firstudata = obj2gco(u);
-  luaC_link(L, obj2gco(u), LUA_TUSERDATA);
-  setbit(u->uv.marked, FIXEDBIT);
-  setbit(L->marked, FIXEDBIT);
   stack_init(L, L);  /* init stack */
   sethvalue(L, gt(L), luaH_new(L, 0, 20));  /* table of globals */
   hvalue(gt(L))->metatable = luaH_new(L, 0, 0);  /* globals metatable */
@@ -100,8 +92,6 @@ static void f_luaopen (lua_State *L, void *ud) {
 
 static void preinit_state (lua_State *L, global_State *g) {
   L->l_G = g;
-  L->tt = LUA_TTHREAD;
-  L->marked = luaC_white(g);
   L->stack = NULL;
   L->stacksize = 0;
   L->errorJmp = NULL;
@@ -136,8 +126,7 @@ static void close_state (lua_State *L) {
 
 lua_State *luaE_newthread (lua_State *L) {
   lua_State *L1 = tostate(luaM_malloc(L, state_size(lua_State)));
-  L1->next = L->next;  /* link new thread after `L' */
-  L->next = obj2gco(L1);
+  luaC_link(L, obj2gco(L1), LUA_TTHREAD);
   preinit_state(L1, G(L));
   stack_init(L1, L);  /* init stack */
   setobj2n(L, gt(L1), gt(L));  /* share table of globals */
@@ -166,11 +155,15 @@ LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
   L = tostate(l);
   g = &((LG *)L)->g;
   L->next = NULL;
-  g->currentwhite = bitmask(WHITE0BIT);
+  L->tt = LUA_TTHREAD;
+  L->marked = g->currentwhite = bitmask(WHITE0BIT);
+  setbit(L->marked, FIXEDBIT);
   preinit_state(L, g);
   g->realloc = f;
   g->ud = ud;
   g->mainthread = L;
+  g->uvhead.u.l.prev = &g->uvhead;
+  g->uvhead.u.l.next = &g->uvhead;
   g->GCthreshold = 0;  /* mark it as unfinished state */
   g->strt.size = 0;
   g->strt.nuse = 0;
@@ -182,7 +175,6 @@ LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
   g->rootgc = obj2gco(L);
   g->sweepstrgc = 0;
   g->sweepgc = &g->rootgc;
-  g->firstudata = NULL;
   g->gray = NULL;
   g->grayagain = NULL;
   g->weak = NULL;
diff --git a/lstate.h b/lstate.h
index 1bb887c4..6c6d32e4 100644
--- a/lstate.h
+++ b/lstate.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.h,v 2.11 2005/01/05 18:20:51 roberto Exp roberto $
+** $Id: lstate.h,v 2.12 2005/01/14 14:19:42 roberto Exp $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -72,7 +72,6 @@ typedef struct global_State {
   lu_byte currentwhite;
   lu_byte gcstate;  /* state of garbage collector */
   GCObject *rootgc;  /* list of all collectable objects */
-  GCObject *firstudata;   /* udata go to the end of `rootgc' */
   GCObject **sweepgc;  /* position of sweep in `rootgc' */
   int sweepstrgc;  /* position of sweep in `strt' */
   GCObject *gray;  /* list of gray objects */
@@ -89,6 +88,7 @@ typedef struct global_State {
   lua_CFunction panic;  /* to be called in unprotected errors */
   TValue _registry;
   struct lua_State *mainthread;
+  UpVal uvhead;  /* head of double-linked list of all open upvalues */
   TString *tmname[TM_N];  /* array with tag-method names */
 } global_State;
 
diff --git a/lstring.c b/lstring.c
index 995f7ccf..0c82220e 100644
--- a/lstring.c
+++ b/lstring.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.c,v 2.4 2004/11/19 15:52:40 roberto Exp roberto $
+** $Id: lstring.c,v 2.5 2004/11/24 19:16:03 roberto Exp $
 ** String table (keeps all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -102,9 +102,9 @@ Udata *luaS_newudata (lua_State *L, size_t s) {
   u->uv.tt = LUA_TUSERDATA;
   u->uv.len = s;
   u->uv.metatable = NULL;
-  /* chain it on udata list */
-  u->uv.next = G(L)->firstudata->uv.next;
-  G(L)->firstudata->uv.next = obj2gco(u);
+  /* chain it on udata list (after main thread) */
+  u->uv.next = G(L)->mainthread->next;
+  G(L)->mainthread->next = obj2gco(u);
   return u;
 }
 
diff --git a/ltests.c b/ltests.c
index 18257905..e99b432f 100644
--- a/ltests.c
+++ b/ltests.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltests.c,v 2.16 2005/01/05 18:20:51 roberto Exp roberto $
+** $Id: ltests.c,v 2.17 2005/01/14 14:19:42 roberto Exp $
 ** Internal Module for Debugging of the Lua Implementation
 ** See Copyright Notice in lua.h
 */
@@ -299,7 +299,7 @@ printf(">>> %d  %s  %02x\n", g->gcstate, luaT_typenames[o->gch.tt], o->gch.marke
     switch (o->gch.tt) {
       case LUA_TUPVAL: {
         UpVal *uv = gco2uv(o);
-        lua_assert(uv->v == &uv->value);  /* must be closed */
+        lua_assert(uv->v == &uv->u.value);  /* must be closed */
         checkvalref(g, o, uv->v);
         break;
       }
@@ -334,14 +334,11 @@ int lua_checkmemory (lua_State *L) {
   global_State *g = G(L);
   GCObject *o;
   checkstack(g, g->mainthread);
-  for (o = g->rootgc; o->gch.tt != LUA_TUSERDATA; o = o->gch.next)
+  for (o = g->rootgc; o != obj2gco(g->mainthread); o = o->gch.next)
     checkobject(g, o);
-  lua_assert(o == g->firstudata);
-  for (; o->gch.tt != LUA_TTHREAD; o = o->gch.next)
-    checkobject(g, o);
-  lua_assert(o == obj2gco(g->mainthread));
-  for (; o; o = o->gch.next) {
-    lua_assert(o->gch.tt == LUA_TTHREAD);
+  checkobject(g, obj2gco(g->mainthread));
+  for (o = g->mainthread->next; o != NULL; o = o->gch.next) {
+    lua_assert(o->gch.tt == LUA_TUSERDATA);
     checkobject(g, o);
   }
   return 0;