From a3d36fe283c09d4e56474da98f22d13162cc9fec Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Tue, 11 Apr 2017 15:41:09 -0300 Subject: Upvalues collected like everything else (with mark-sweep) instead of reference count (simpler and better for generational mode) --- lapi.c | 25 +++++++----------- lfunc.c | 47 +++++++++++++++++++-------------- lfunc.h | 18 ++----------- lgc.c | 89 +++++++++++++++++++++++---------------------------------------- lgc.h | 10 +------ lobject.h | 22 ++++++++++++---- lstate.h | 4 ++- ltm.c | 4 +-- lvm.c | 5 ++-- 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) { -- cgit v1.2.3-55-g6feb