Upvalues collected like everything else (with mark-sweep) instead

of reference count (simpler and better for generational mode)

9 files changed, 97 insertions, 127 deletions

diff --git a/lapi.c b/lapi.c
index 25ed81fd..eb67d090 100644
--- a/lapi.c
+++ b/lapi.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lapi.c,v 2.260 2017/02/23 21:07:34 roberto Exp roberto $
+** $Id: lapi.c,v 2.261 2017/04/06 13:08:56 roberto Exp roberto $
 ** Lua API
 ** See Copyright Notice in lua.h
 */
@@ -1004,7 +1004,7 @@ LUA_API int lua_load (lua_State *L, lua_Reader reader, void *data,
       const TValue *gt = luaH_getint(reg, LUA_RIDX_GLOBALS);
       /* set global table as 1st upvalue of 'f' (may be LUA_ENV) */
       setobj(L, f->upvals[0]->v, gt);
-      luaC_upvalbarrier(L, f->upvals[0], gt);
+      luaC_barrier(L, f->upvals[0], gt);
     }
   }
   lua_unlock(L);
@@ -1202,13 +1202,13 @@ LUA_API void *lua_newuserdata (lua_State *L, size_t size) {
 
 
 static const char *aux_upvalue (StkId fi, int n, TValue **val,
-                                CClosure **owner, UpVal **uv) {
+                                GCObject **owner) {
   switch (ttype(fi)) {
     case LUA_TCCL: {  /* C closure */
       CClosure *f = clCvalue(fi);
       if (!(1 <= n && n <= f->nupvalues)) return NULL;
       *val = &f->upvalue[n-1];
-      if (owner) *owner = f;
+      if (owner) *owner = obj2gco(f);
       return "";
     }
     case LUA_TLCL: {  /* Lua closure */
@@ -1217,7 +1217,7 @@ static const char *aux_upvalue (StkId fi, int n, TValue **val,
       Proto *p = f->p;
       if (!(1 <= n && n <= p->sizeupvalues)) return NULL;
       *val = f->upvals[n-1]->v;
-      if (uv) *uv = f->upvals[n - 1];
+      if (owner) *owner = obj2gco(f->upvals[n - 1]);
       name = p->upvalues[n-1].name;
       return (name == NULL) ? "(*no name)" : getstr(name);
     }
@@ -1230,7 +1230,7 @@ LUA_API const char *lua_getupvalue (lua_State *L, int funcindex, int n) {
   const char *name;
   TValue *val = NULL;  /* to avoid warnings */
   lua_lock(L);
-  name = aux_upvalue(index2addr(L, funcindex), n, &val, NULL, NULL);
+  name = aux_upvalue(index2addr(L, funcindex), n, &val, NULL);
   if (name) {
     setobj2s(L, L->top, val);
     api_incr_top(L);
@@ -1243,18 +1243,16 @@ LUA_API const char *lua_getupvalue (lua_State *L, int funcindex, int n) {
 LUA_API const char *lua_setupvalue (lua_State *L, int funcindex, int n) {
   const char *name;
   TValue *val = NULL;  /* to avoid warnings */
-  CClosure *owner = NULL;
-  UpVal *uv = NULL;
+  GCObject *owner = NULL;  /* to avoid warnings */
   StkId fi;
   lua_lock(L);
   fi = index2addr(L, funcindex);
   api_checknelems(L, 1);
-  name = aux_upvalue(fi, n, &val, &owner, &uv);
+  name = aux_upvalue(fi, n, &val, &owner);
   if (name) {
     L->top--;
     setobj(L, val, L->top);
-    if (owner) { luaC_barrier(L, owner, val); }
-    else if (uv) { luaC_upvalbarrier(L, uv, val); }
+    luaC_barrier(L, owner, val);
   }
   lua_unlock(L);
   return name;
@@ -1296,11 +1294,8 @@ LUA_API void lua_upvaluejoin (lua_State *L, int fidx1, int n1,
   LClosure *f1;
   UpVal **up1 = getupvalref(L, fidx1, n1, &f1);
   UpVal **up2 = getupvalref(L, fidx2, n2, NULL);
-  luaC_upvdeccount(L, *up1);
   *up1 = *up2;
-  (*up1)->refcount++;
-  if (upisopen(*up1)) (*up1)->u.open.touched = 1;
-  luaC_upvalbarrier(L, *up1, (*up1)->v);
+  luaC_objbarrier(L, f1, *up1);
 }
 
 
diff --git a/lfunc.c b/lfunc.c
index 0f839e7c..898104ac 100644
--- a/lfunc.c
+++ b/lfunc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lfunc.c,v 2.45 2014/11/02 19:19:04 roberto Exp roberto $
+** $Id: lfunc.c,v 2.46 2017/04/06 13:08:56 roberto Exp roberto $
 ** Auxiliary functions to manipulate prototypes and closures
 ** See Copyright Notice in lua.h
 */
@@ -45,31 +45,35 @@ LClosure *luaF_newLclosure (lua_State *L, int n) {
 void luaF_initupvals (lua_State *L, LClosure *cl) {
   int i;
   for (i = 0; i < cl->nupvalues; i++) {
-    UpVal *uv = luaM_new(L, UpVal);
-    uv->refcount = 1;
+    GCObject *o = luaC_newobj(L, LUA_TUPVAL, sizeof(UpVal));
+    UpVal *uv = gco2upv(o);
     uv->v = &uv->u.value;  /* make it closed */
     setnilvalue(uv->v);
     cl->upvals[i] = uv;
+    luaC_objbarrier(L, cl, o);
   }
 }
 
 
 UpVal *luaF_findupval (lua_State *L, StkId level) {
   UpVal **pp = &L->openupval;
+  GCObject *o;
   UpVal *p;
   UpVal *uv;
   lua_assert(isintwups(L) || L->openupval == NULL);
-  while (*pp != NULL && (p = *pp)->v >= level) {
+  while ((p = *pp) != NULL && p->v >= level) {
     lua_assert(upisopen(p));
     if (p->v == level)  /* found a corresponding upvalue? */
       return p;  /* return it */
     pp = &p->u.open.next;
   }
-  /* not found: create a new upvalue */
-  uv = luaM_new(L, UpVal);
-  uv->refcount = 0;
-  uv->u.open.next = *pp;  /* link it to list of open upvalues */
-  uv->u.open.touched = 1;
+  /* not found: create a new upvalue between 'pp' and 'p' */
+  o = luaC_newobj(L, LUA_TUPVAL, sizeof(UpVal));
+  uv = gco2upv(o);
+  uv->u.open.next = p;  /* link it to list of open upvalues */
+  uv->u.open.previous = pp;
+  if (p)
+    p->u.open.previous = &uv->u.open.next;
   *pp = uv;
   uv->v = level;  /* current value lives in the stack */
   if (!isintwups(L)) {  /* thread not in list of threads with upvalues? */
@@ -80,19 +84,24 @@ UpVal *luaF_findupval (lua_State *L, StkId level) {
 }
 
 
+void luaF_unlinkupval (UpVal *uv) {
+  lua_assert(upisopen(uv));
+  *uv->u.open.previous = uv->u.open.next;
+  if (uv->u.open.next)
+    uv->u.open.next->u.open.previous = uv->u.open.previous;
+}
+
+
 void luaF_close (lua_State *L, StkId level) {
   UpVal *uv;
   while (L->openupval != NULL && (uv = L->openupval)->v >= level) {
-    lua_assert(upisopen(uv));
-    L->openupval = uv->u.open.next;  /* remove from 'open' list */
-    if (uv->refcount == 0)  /* no references? */
-      luaM_free(L, uv);  /* free upvalue */
-    else {
-      TValue *slot = &uv->u.value;  /* new position for value */
-      setobj(L, slot, uv->v);  /* move value to upvalue slot */
-      uv->v = slot;  /* now current value lives here */
-      luaC_upvalbarrier(L, uv, slot);
-    }
+    TValue *slot = &uv->u.value;  /* new position for value */
+    luaF_unlinkupval(uv);
+    setobj(L, slot, uv->v);  /* move value to upvalue slot */
+    uv->v = slot;  /* now current value lives here */
+    if (!iswhite(uv))
+      gray2black(uv);  /* closed upvalues cannot be gray */
+    luaC_barrier(L, uv, slot);
   }
 }
 
diff --git a/lfunc.h b/lfunc.h
index 6fd3fbac..7d0eca4a 100644
--- a/lfunc.h
+++ b/lfunc.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lfunc.h,v 2.14 2014/06/19 18:27:20 roberto Exp roberto $
+** $Id: lfunc.h,v 2.15 2015/01/13 15:49:11 roberto Exp roberto $
 ** Auxiliary functions to manipulate prototypes and closures
 ** See Copyright Notice in lua.h
 */
@@ -29,21 +29,6 @@
 #define MAXUPVAL        255
 
 
-/*
-** Upvalues for Lua closures
-*/
-struct UpVal {
-  TValue *v;  /* points to stack or to its own value */
-  lu_mem refcount;  /* reference counter */
-  union {
-    struct {  /* (when open) */
-      UpVal *next;  /* linked list */
-      int touched;  /* mark to avoid cycles with dead threads */
-    } open;
-    TValue value;  /* the value (when closed) */
-  } u;
-};
-
 #define upisopen(up)    ((up)->v != &(up)->u.value)
 
 
@@ -53,6 +38,7 @@ LUAI_FUNC LClosure *luaF_newLclosure (lua_State *L, int nelems);
 LUAI_FUNC void luaF_initupvals (lua_State *L, LClosure *cl);
 LUAI_FUNC UpVal *luaF_findupval (lua_State *L, StkId level);
 LUAI_FUNC void luaF_close (lua_State *L, StkId level);
+LUAI_FUNC void luaF_unlinkupval (UpVal *uv);
 LUAI_FUNC void luaF_freeproto (lua_State *L, Proto *f);
 LUAI_FUNC const char *luaF_getlocalname (const Proto *func, int local_number,
                                          int pc);
diff --git a/lgc.c b/lgc.c
index 68a7622f..f4223588 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 2.218 2017/04/06 13:08:56 roberto Exp roberto $
+** $Id: lgc.c,v 2.219 2017/04/10 13:33:04 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -179,25 +179,11 @@ void luaC_barrierback_ (lua_State *L, Table *t) {
 }
 
 
-/*
-** barrier for assignments to closed upvalues. Because upvalues are
-** shared among closures, it is impossible to know the color of all
-** closures pointing to it. So, we assume that the object being assigned
-** must be marked.
-*/
-void luaC_upvalbarrier_ (lua_State *L, GCObject *o) {
-  global_State *g = G(L);
-  if (keepinvariant(g) && !isold(o)) {
-    markobject(g, o);
-    setage(o, G_OLD0);
-  }
-}
-
-
 void luaC_fix (lua_State *L, GCObject *o) {
   global_State *g = G(L);
   lua_assert(g->allgc == o);  /* object must be 1st in 'allgc' list! */
   white2gray(o);  /* they will be gray forever */
+  setage(o, G_OLD);  /* and old forever */
   g->allgc = o->next;  /* remove object from 'allgc' list */
   o->next = g->fixedgc;  /* link it to 'fixedgc' list */
   g->fixedgc = o;
@@ -230,10 +216,11 @@ GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
 
 
 /*
-** mark an object. Userdata, strings, and closed upvalues are visited
+** Mark an object. Userdata, strings, and closed upvalues are visited
 ** and turned black here. Other objects are marked gray and added
 ** to appropriate list to be visited (and turned black) later. (Open
-** upvalues are already linked in 'headuv' list.)
+** upvalues are already linked in 'headuv' list. They are kept gray
+** to avoid barriers, as their values will be revisited by the thread.)
 */
 static void reallymarkobject (global_State *g, GCObject *o) {
  reentry:
@@ -261,6 +248,14 @@ static void reallymarkobject (global_State *g, GCObject *o) {
       }
       break;
     }
+    case LUA_TUPVAL: {
+      UpVal *uv = gco2upv(o);
+      g->GCmemtrav += sizeof(UpVal);
+      if (!upisopen(uv))  /* open upvalues are kept gray */
+        gray2black(o);
+      markvalue(g, uv->v);  /* mark its content */
+      break;
+    }
     case LUA_TLCL: {
       linkgclist(gco2lcl(o), g->gray);
       break;
@@ -324,10 +319,8 @@ static void remarkupvals (global_State *g) {
       *p = thread->twups;  /* remove thread from the list */
       thread->twups = thread;  /* mark that it is out of list */
       for (uv = thread->openupval; uv != NULL; uv = uv->u.open.next) {
-        if (uv->u.open.touched) {
-          markvalue(g, uv->v);  /* remark upvalue's value */
-          uv->u.open.touched = 0;
-        }
+        if (!iswhite(uv))  /* upvalue already visited? */
+          markvalue(g, uv->v);  /* mark its value */
       }
     }
   }
@@ -516,22 +509,15 @@ static lu_mem traverseCclosure (global_State *g, CClosure *cl) {
 }
 
 /*
-** open upvalues point to values in a thread, so those values should
-** be marked when the thread is traversed except in the atomic phase
-** (because then the value cannot be changed by the thread and the
-** thread may not be traversed again)
+** Traverse a Lua closure, marking its prototype and its upvalues.
+** (Both can be NULL while closure is being created.)
 */
 static lu_mem traverseLclosure (global_State *g, LClosure *cl) {
   int i;
   markobjectN(g, cl->p);  /* mark its prototype */
   for (i = 0; i < cl->nupvalues; i++) {  /* visit its upvalues */
     UpVal *uv = cl->upvals[i];
-    if (uv != NULL) {  /* can be NULL while closure is being built */
-      if (upisopen(uv) && g->gcstate != GCSatomic)
-        uv->u.open.touched = 1;  /* can be marked in 'remarkupvals' */
-      else
-        markvalue(g, uv->v);
-    }
+    markobjectN(g, uv);  /* mark upvalue */
   }
   return sizeLclosure(cl->nupvalues);
 }
@@ -569,7 +555,6 @@ static lu_mem traversethread (global_State *g, lua_State *th) {
 static void propagatemark (global_State *g) {
   lu_mem size;
   GCObject *o = g->gray;
-  lua_assert(ongraylist(o));
   gray2black(o);
   switch (o->tt) {
     case LUA_TTABLE: {
@@ -683,26 +668,10 @@ static void clearvalues (global_State *g, GCObject *l, GCObject *f) {
 }
 
 
-/*
-** Decrement the reference count of an upvalue. If it goes to zero and
-** upvalue is closed, delete it.
-*/
-void luaC_upvdeccount (lua_State *L, UpVal *uv) {
-  lua_assert(uv->refcount > 0);
-  uv->refcount--;
-  if (uv->refcount == 0 && !upisopen(uv))
-    luaM_free(L, uv);
-}
-
-
-static void freeLclosure (lua_State *L, LClosure *cl) {
-  int i;
-  for (i = 0; i < cl->nupvalues; i++) {
-    UpVal *uv = cl->upvals[i];
-    if (uv)
-      luaC_upvdeccount(L, uv);
-  }
-  luaM_freemem(L, cl, sizeLclosure(cl->nupvalues));
+static void freeupval (lua_State *L, UpVal *uv) {
+  if (upisopen(uv))
+    luaF_unlinkupval(uv);
+  luaM_free(L, uv);
 }
 
 
@@ -711,8 +680,11 @@ static void freeobj (lua_State *L, GCObject *o) {
     case LUA_TPROTO:
       luaF_freeproto(L, gco2p(o));
       break;
+    case LUA_TUPVAL:
+      freeupval(L, gco2upv(o));
+      break;
     case LUA_TLCL:
-      freeLclosure(L, gco2lcl(o));
+      luaM_freemem(L, o, sizeLclosure(gco2lcl(o)->nupvalues));
       break;
     case LUA_TCCL:
       luaM_freemem(L, o, sizeCclosure(gco2ccl(o)->nupvalues));
@@ -1144,14 +1116,14 @@ static void correctgraylists (global_State *g) {
 
 
 /*
-** Mark 'old1' objects when starting a new young collection. ('old1'
-** tables are always black, threads are always gray.)
+** Mark 'old1' objects when starting a new young collection. (Threads
+** and open upvalues are always gray, and do not need to be marked.
+** All other old objects are black.)
 */
 static void markold (global_State *g, GCObject *from, GCObject *to) {
   GCObject *p;
   for (p = from; p != to; p = p->next) {
     if (getage(p) == G_OLD1) {
-      lua_assert((p->tt == LUA_TTHREAD) ? isgray(p) : isblack(p));
       if (isblack(p)) {
         black2gray(p);  /* should be '2white', but gray works too */
         reallymarkobject(g, p);
@@ -1228,6 +1200,8 @@ static void entergen (lua_State *L, global_State *g) {
 
   sweep2old(L, &g->tobefnz);
 
+  setage(g->mainthread, G_OLD);
+
   finishgencycle(L, g);
   g->gckind = KGC_GEN;
 }
@@ -1282,6 +1256,7 @@ static void genstep (lua_State *L, global_State *g) {
   youngcollection(L, g);
   mem = gettotalbytes(g);
   luaE_setdebt(g, -((mem / 100) * 20));
+lua_checkmemory(L);
 }
 
 
diff --git a/lgc.h b/lgc.h
index 13896d42..396f5a4e 100644
--- a/lgc.h
+++ b/lgc.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.h,v 2.94 2017/04/06 13:08:56 roberto Exp roberto $
+** $Id: lgc.h,v 2.95 2017/04/10 13:33:04 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -124,8 +124,6 @@
 #define changeage(o,f,t)  \
         check_exp(getage(o) == (f), (o)->marked ^= ((f)^(t)))
 
-#define ongraylist(o)   (isgray(o) || getage(o) == G_TOUCHED2)
-
 
 /*
 ** Does one step of collection when debt becomes positive. 'pre'/'pos'
@@ -153,10 +151,6 @@
         (isblack(p) && iswhite(o)) ? \
         luaC_barrier_(L,obj2gco(p),obj2gco(o)) : cast_void(0))
 
-#define luaC_upvalbarrier(L,uv,x) ( \
-        (iscollectable(x) && !upisopen(uv)) ? \
-         luaC_upvalbarrier_(L,gcvalue(x)) : cast_void(0))
-
 LUAI_FUNC void luaC_fix (lua_State *L, GCObject *o);
 LUAI_FUNC void luaC_freeallobjects (lua_State *L);
 LUAI_FUNC void luaC_step (lua_State *L);
@@ -165,9 +159,7 @@ LUAI_FUNC void luaC_fullgc (lua_State *L, int isemergency);
 LUAI_FUNC GCObject *luaC_newobj (lua_State *L, int tt, size_t sz);
 LUAI_FUNC void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v);
 LUAI_FUNC void luaC_barrierback_ (lua_State *L, Table *o);
-LUAI_FUNC void luaC_upvalbarrier_ (lua_State *L, GCObject *o);
 LUAI_FUNC void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt);
-LUAI_FUNC void luaC_upvdeccount (lua_State *L, UpVal *uv);
 LUAI_FUNC void luaC_changemode (lua_State *L, int newmode);
 
 
diff --git a/lobject.h b/lobject.h
index eeddfdef..7c521ba2 100644
--- a/lobject.h
+++ b/lobject.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lobject.h,v 2.116 2015/11/03 18:33:10 roberto Exp roberto $
+** $Id: lobject.h,v 2.117 2016/08/01 19:51:24 roberto Exp roberto $
 ** Type definitions for Lua objects
 ** See Copyright Notice in lua.h
 */
@@ -19,8 +19,9 @@
 /*
 ** Extra tags for non-values
 */
-#define LUA_TPROTO      LUA_NUMTAGS             /* function prototypes */
-#define LUA_TDEADKEY    (LUA_NUMTAGS+1)         /* removed keys in tables */
+#define LUA_TUPVAL      LUA_NUMTAGS  /* upvalues */
+#define LUA_TPROTO      (LUA_NUMTAGS+1)  /* function prototypes */
+#define LUA_TDEADKEY    (LUA_NUMTAGS+2)  /* removed keys in tables */
 
 /*
 ** number of all possible tags (including LUA_TNONE but excluding DEADKEY)
@@ -431,9 +432,20 @@ typedef struct Proto {
 
 
 /*
-** Lua Upvalues
+** Upvalues for Lua closures
 */
-typedef struct UpVal UpVal;
+typedef struct UpVal {
+  CommonHeader;
+  TValue *v;  /* points to stack or to its own value */
+  union {
+    struct {  /* (when open) */
+      struct UpVal *next;  /* linked list */
+      struct UpVal **previous;
+    } open;
+    TValue value;  /* the value (when closed) */
+  } u;
+} UpVal;
+
 
 
 /*
diff --git a/lstate.h b/lstate.h
index b01859aa..dc74370b 100644
--- a/lstate.h
+++ b/lstate.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.h,v 2.135 2017/02/23 21:07:34 roberto Exp $
+** $Id: lstate.h,v 2.136 2017/04/05 16:50:51 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -224,6 +224,7 @@ union GCUnion {
   struct Table h;
   struct Proto p;
   struct lua_State th;  /* thread */
+  struct UpVal upv;
 };
 
 
@@ -240,6 +241,7 @@ union GCUnion {
 #define gco2t(o)  check_exp((o)->tt == LUA_TTABLE, &((cast_u(o))->h))
 #define gco2p(o)  check_exp((o)->tt == LUA_TPROTO, &((cast_u(o))->p))
 #define gco2th(o)  check_exp((o)->tt == LUA_TTHREAD, &((cast_u(o))->th))
+#define gco2upv(o)  check_exp((o)->tt == LUA_TUPVAL, &((cast_u(o))->upv))
 
 
 /* macro to convert a Lua object into a GCObject */
diff --git a/ltm.c b/ltm.c
index b664dbed..47341384 100644
--- a/ltm.c
+++ b/ltm.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltm.c,v 2.37 2016/02/26 19:20:15 roberto Exp roberto $
+** $Id: ltm.c,v 2.38 2016/12/22 13:08:50 roberto Exp roberto $
 ** Tag methods
 ** See Copyright Notice in lua.h
 */
@@ -30,7 +30,7 @@ LUAI_DDEF const char *const luaT_typenames_[LUA_TOTALTAGS] = {
   "no value",
   "nil", "boolean", udatatypename, "number",
   "string", "table", "function", udatatypename, "thread",
-  "proto" /* this last case is used for tests only */
+  "upvalue", "proto" /* these last cases are used for tests only */
 };
 
 
diff --git a/lvm.c b/lvm.c
index 81b2a481..32958665 100644
--- a/lvm.c
+++ b/lvm.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lvm.c,v 2.268 2016/02/05 19:59:14 roberto Exp roberto $
+** $Id: lvm.c,v 2.269 2017/04/06 13:08:56 roberto Exp roberto $
 ** Lua virtual machine
 ** See Copyright Notice in lua.h
 */
@@ -642,7 +642,6 @@ static void pushclosure (lua_State *L, Proto *p, UpVal **encup, StkId base,
       ncl->upvals[i] = luaF_findupval(L, base + uv[i].idx);
     else  /* get upvalue from enclosing function */
       ncl->upvals[i] = encup[uv[i].idx];
-    ncl->upvals[i]->refcount++;
     /* new closure is white, so we do not need a barrier here */
   }
   if (!isblack(p))  /* cache will not break GC invariant? */
@@ -855,7 +854,7 @@ void luaV_execute (lua_State *L) {
       vmcase(OP_SETUPVAL) {
         UpVal *uv = cl->upvals[GETARG_B(i)];
         setobj(L, uv->v, ra);
-        luaC_upvalbarrier(L, uv, ra);
+        luaC_barrier(L, uv, ra);
         vmbreak;
       }
       vmcase(OP_SETTABLE) {