Update lua plugin to 5.2.3

Prior to this patch the Lua plugin used version 5.1.4. This change
reduces the number of modifications in the Lua source using some new
defines and because the upstream source is now more flexible.

Unless otherwise stated, l*.[ch] files are taken unmodified from the
upstream lua-5.2.3.

fscanf.c:
file descriptors in rockbox are just ints, they are hidden behind a
void* now so liolib requires less modifications. fscanf is updated to
use void* too.

getc.c: this is a new file required for getc implementation in lauxlib.c

lauxlib.c: LoadF replaced FILE* with int, the rockbox file
descriptor int are cast to FILE* (actually void* due to typedef).
getc uses the PREFIX version. stdin is not used, as per 5.1.4.

lbaselib.c: now uses strspn in the number parsing. print uses DEBUGF now
rather than being commented out.

lbitlib.c: use the built-in version from 5.2.3 rather than Reuben
Thomas's external library. Backwards compatible and adds some new bit
operations.

ldo.c: the LUAI_THROW/TRY defines are now in the core lua code, so have
been removed from rockconf.h

liolib.c: here the implementation has changed to use the LStream from
the original source, and cast the FILE* pointers to int. This has
reduced the number of modifications from the upstream version.

llex.c: the only change from upstream is to remove the locale include.

lmathlib.c: updated from the 5.2.3 version and re-applied the changes
that were made vs 5.1.4 for random numbers and to remove unsupported
float functions.

loadlib.c: upstream version, with the 5.1.4 changes for missing
functions.

lobject.c: upstream version, with ctype.h added and sprintf changed to
snprintf.

loslib.c: upstream version with locale.h removed and 5.1.4 changes for
unsupportable functions.

lstrlib.c: sprintf changed to snprintf.

ltable.c: upstream with the hashnum function from 5.1.4 to avoid frexp
in luai_hashnum.

luaconf.h: updated to 5.2.3 version, restored relevant parts from the
original 5.1.4 configuration. The COMPAT defines that are no longer
available are not included.

lundump.c: VERSION macro conflicts with the core Rockbox equivalent.

rocklib.c: luaL_reg is no longer available, replaced by luaL_Reg
equivalent. Moved checkboolean/optboolean functions to this file and out
of core lua files. luaL_getn is no longer available, replaced by
luaL_rawlen. luaL_register is deprecated, use the newlib/setfuncs
replacements. rli_init has to be called before setting up the newlib to
avoid overwriting the rb table.

rocklib_aux.pl: use rli_checkboolean from rocklib.c.

rocklua.c: new default bits library used, update the library loading
code with idiomatic 5.2 code.

strcspn.c: no longer needed, but strspn.c is required for strspn in
lbaselib.c

Change-Id: I0c7945c755f79083afe98ec117e1e8cf13de2651
Reviewed-on: http://gerrit.rockbox.org/774
Tested: Richard Quirk <richard.quirk@gmail.com>
Reviewed-by: Marcin Bukat <marcin.bukat@gmail.com>

1 files changed, 963 insertions, 454 deletions

diff --git a/apps/plugins/lua/lgc.c b/apps/plugins/lua/lgc.c
index d9e0b78294..52460dcdd5 100644
--- a/apps/plugins/lua/lgc.c
+++ b/apps/plugins/lua/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 2.38.1.1 2007/12/27 13:02:25 roberto Exp $
+** $Id: lgc.c,v 2.140.1.2 2013/04/26 18:22:05 roberto Exp $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -23,376 +23,663 @@
 #include "ltm.h"
 
 
-#define GCSTEPSIZE      1024u
-#define GCSWEEPMAX      40
-#define GCSWEEPCOST     10
-#define GCFINALIZECOST  100
 
+/*
+** cost of sweeping one element (the size of a small object divided
+** by some adjust for the sweep speed)
+*/
+#define GCSWEEPCOST     ((sizeof(TString) + 4) / 4)
 
-#define maskmarks       cast_byte(~(bitmask(BLACKBIT)|WHITEBITS))
+/* maximum number of elements to sweep in each single step */
+#define GCSWEEPMAX      (cast_int((GCSTEPSIZE / GCSWEEPCOST) / 4))
 
-#define makewhite(g,x)  \
-   ((x)->gch.marked = cast_byte(((x)->gch.marked & maskmarks) | luaC_white(g)))
+/* maximum number of finalizers to call in each GC step */
+#define GCFINALIZENUM   4
+
+
+/*
+** macro to adjust 'stepmul': 'stepmul' is actually used like
+** 'stepmul / STEPMULADJ' (value chosen by tests)
+*/
+#define STEPMULADJ              200
+
+
+/*
+** macro to adjust 'pause': 'pause' is actually used like
+** 'pause / PAUSEADJ' (value chosen by tests)
+*/
+#define PAUSEADJ                100
 
-#define white2gray(x)   reset2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT)
-#define black2gray(x)   resetbit((x)->gch.marked, BLACKBIT)
 
-#define stringmark(s)   reset2bits((s)->tsv.marked, WHITE0BIT, WHITE1BIT)
+/*
+** 'makewhite' erases all color bits plus the old bit and then
+** sets only the current white bit
+*/
+#define maskcolors      (~(bit2mask(BLACKBIT, OLDBIT) | WHITEBITS))
+#define makewhite(g,x)  \
+ (gch(x)->marked = cast_byte((gch(x)->marked & maskcolors) | luaC_white(g)))
 
+#define white2gray(x)   resetbits(gch(x)->marked, WHITEBITS)
+#define black2gray(x)   resetbit(gch(x)->marked, BLACKBIT)
 
-#define isfinalized(u)          testbit((u)->marked, FINALIZEDBIT)
-#define markfinalized(u)        l_setbit((u)->marked, FINALIZEDBIT)
 
+#define isfinalized(x)          testbit(gch(x)->marked, FINALIZEDBIT)
 
-#define KEYWEAK         bitmask(KEYWEAKBIT)
-#define VALUEWEAK       bitmask(VALUEWEAKBIT)
+#define checkdeadkey(n) lua_assert(!ttisdeadkey(gkey(n)) || ttisnil(gval(n)))
 
 
+#define checkconsistency(obj)  \
+  lua_longassert(!iscollectable(obj) || righttt(obj))
+
 
 #define markvalue(g,o) { checkconsistency(o); \
-  if (iscollectable(o) && iswhite(gcvalue(o))) reallymarkobject(g,gcvalue(o)); }
+  if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); }
 
-#define markobject(g,t) { if (iswhite(obj2gco(t))) \
+#define markobject(g,t) { if ((t) && iswhite(obj2gco(t))) \
                 reallymarkobject(g, obj2gco(t)); }
 
+static void reallymarkobject (global_State *g, GCObject *o);
+
+
+/*
+** {======================================================
+** Generic functions
+** =======================================================
+*/
+
+
+/*
+** one after last element in a hash array
+*/
+#define gnodelast(h)    gnode(h, cast(size_t, sizenode(h)))
+
 
-#define setthreshold(g)  (g->GCthreshold = (g->estimate/100) * g->gcpause)
+/*
+** link table 'h' into list pointed by 'p'
+*/
+#define linktable(h,p)  ((h)->gclist = *(p), *(p) = obj2gco(h))
 
 
+/*
+** if key is not marked, mark its entry as dead (therefore removing it
+** from the table)
+*/
 static void removeentry (Node *n) {
   lua_assert(ttisnil(gval(n)));
-  if (iscollectable(gkey(n)))
-    setttype(gkey(n), LUA_TDEADKEY);  /* dead key; remove it */
+  if (valiswhite(gkey(n)))
+    setdeadvalue(gkey(n));  /* unused and unmarked key; remove it */
+}
+
+
+/*
+** tells whether a key or value can be cleared from a weak
+** table. Non-collectable objects are never removed from weak
+** tables. Strings behave as `values', so are never removed too. for
+** other objects: if really collected, cannot keep them; for objects
+** being finalized, keep them in keys, but not in values
+*/
+static int iscleared (global_State *g, const TValue *o) {
+  if (!iscollectable(o)) return 0;
+  else if (ttisstring(o)) {
+    markobject(g, rawtsvalue(o));  /* strings are `values', so are never weak */
+    return 0;
+  }
+  else return iswhite(gcvalue(o));
 }
 
 
+/*
+** barrier that moves collector forward, that is, mark the white object
+** being pointed by a black object.
+*/
+void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
+  global_State *g = G(L);
+  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
+  lua_assert(g->gcstate != GCSpause);
+  lua_assert(gch(o)->tt != LUA_TTABLE);
+  if (keepinvariantout(g))  /* must keep invariant? */
+    reallymarkobject(g, v);  /* restore invariant */
+  else {  /* sweep phase */
+    lua_assert(issweepphase(g));
+    makewhite(g, o);  /* mark main obj. as white to avoid other barriers */
+  }
+}
+
+
+/*
+** barrier that moves collector backward, that is, mark the black object
+** pointing to a white object as gray again. (Current implementation
+** only works for tables; access to 'gclist' is not uniform across
+** different types.)
+*/
+void luaC_barrierback_ (lua_State *L, GCObject *o) {
+  global_State *g = G(L);
+  lua_assert(isblack(o) && !isdead(g, o) && gch(o)->tt == LUA_TTABLE);
+  black2gray(o);  /* make object gray (again) */
+  gco2t(o)->gclist = g->grayagain;
+  g->grayagain = o;
+}
+
+
+/*
+** barrier for prototypes. When creating first closure (cache is
+** NULL), use a forward barrier; this may be the only closure of the
+** prototype (if it is a "regular" function, with a single instance)
+** and the prototype may be big, so it is better to avoid traversing
+** it again. Otherwise, use a backward barrier, to avoid marking all
+** possible instances.
+*/
+LUAI_FUNC void luaC_barrierproto_ (lua_State *L, Proto *p, Closure *c) {
+  global_State *g = G(L);
+  lua_assert(isblack(obj2gco(p)));
+  if (p->cache == NULL) {  /* first time? */
+    luaC_objbarrier(L, p, c);
+  }
+  else {  /* use a backward barrier */
+    black2gray(obj2gco(p));  /* make prototype gray (again) */
+    p->gclist = g->grayagain;
+    g->grayagain = obj2gco(p);
+  }
+}
+
+
+/*
+** check color (and invariants) for an upvalue that was closed,
+** i.e., moved into the 'allgc' list
+*/
+void luaC_checkupvalcolor (global_State *g, UpVal *uv) {
+  GCObject *o = obj2gco(uv);
+  lua_assert(!isblack(o));  /* open upvalues are never black */
+  if (isgray(o)) {
+    if (keepinvariant(g)) {
+      resetoldbit(o);  /* see MOVE OLD rule */
+      gray2black(o);  /* it is being visited now */
+      markvalue(g, uv->v);
+    }
+    else {
+      lua_assert(issweepphase(g));
+      makewhite(g, o);
+    }
+  }
+}
+
+
+/*
+** create a new collectable object (with given type and size) and link
+** it to '*list'. 'offset' tells how many bytes to allocate before the
+** object itself (used only by states).
+*/
+GCObject *luaC_newobj (lua_State *L, int tt, size_t sz, GCObject **list,
+                       int offset) {
+  global_State *g = G(L);
+  char *raw = cast(char *, luaM_newobject(L, novariant(tt), sz));
+  GCObject *o = obj2gco(raw + offset);
+  if (list == NULL)
+    list = &g->allgc;  /* standard list for collectable objects */
+  gch(o)->marked = luaC_white(g);
+  gch(o)->tt = tt;
+  gch(o)->next = *list;
+  *list = o;
+  return o;
+}
+
+/* }====================================================== */
+
+
+
+/*
+** {======================================================
+** Mark functions
+** =======================================================
+*/
+
+
+/*
+** 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.)
+*/
 static void reallymarkobject (global_State *g, GCObject *o) {
-  lua_assert(iswhite(o) && !isdead(g, o));
+  lu_mem size;
   white2gray(o);
-  switch (o->gch.tt) {
-    case LUA_TSTRING: {
-      return;
+  switch (gch(o)->tt) {
+    case LUA_TSHRSTR:
+    case LUA_TLNGSTR: {
+      size = sizestring(gco2ts(o));
+      break;  /* nothing else to mark; make it black */
     }
     case LUA_TUSERDATA: {
       Table *mt = gco2u(o)->metatable;
-      gray2black(o);  /* udata are never gray */
-      if (mt) markobject(g, mt);
+      markobject(g, mt);
       markobject(g, gco2u(o)->env);
-      return;
+      size = sizeudata(gco2u(o));
+      break;
     }
     case LUA_TUPVAL: {
       UpVal *uv = gco2uv(o);
       markvalue(g, uv->v);
-      if (uv->v == &uv->u.value)  /* closed? */
-        gray2black(o);  /* open upvalues are never black */
+      if (uv->v != &uv->u.value)  /* open? */
+        return;  /* open upvalues remain gray */
+      size = sizeof(UpVal);
+      break;
+    }
+    case LUA_TLCL: {
+      gco2lcl(o)->gclist = g->gray;
+      g->gray = o;
       return;
     }
-    case LUA_TFUNCTION: {
-      gco2cl(o)->c.gclist = g->gray;
+    case LUA_TCCL: {
+      gco2ccl(o)->gclist = g->gray;
       g->gray = o;
-      break;
+      return;
     }
     case LUA_TTABLE: {
-      gco2h(o)->gclist = g->gray;
-      g->gray = o;
-      break;
+      linktable(gco2t(o), &g->gray);
+      return;
     }
     case LUA_TTHREAD: {
       gco2th(o)->gclist = g->gray;
       g->gray = o;
-      break;
+      return;
     }
     case LUA_TPROTO: {
       gco2p(o)->gclist = g->gray;
       g->gray = o;
-      break;
+      return;
     }
-    default: lua_assert(0);
+    default: lua_assert(0); return;
   }
+  gray2black(o);
+  g->GCmemtrav += size;
+}
+
+
+/*
+** mark metamethods for basic types
+*/
+static void markmt (global_State *g) {
+  int i;
+  for (i=0; i < LUA_NUMTAGS; i++)
+    markobject(g, g->mt[i]);
 }
 
 
-static void marktmu (global_State *g) {
-  GCObject *u = g->tmudata;
-  if (u) {
-    do {
-      u = u->gch.next;
-      makewhite(g, u);  /* may be marked, if left from previous GC */
-      reallymarkobject(g, u);
-    } while (u != g->tmudata);
+/*
+** mark all objects in list of being-finalized
+*/
+static void markbeingfnz (global_State *g) {
+  GCObject *o;
+  for (o = g->tobefnz; o != NULL; o = gch(o)->next) {
+    makewhite(g, o);
+    reallymarkobject(g, o);
   }
 }
 
 
-/* move `dead' udata that need finalization to list `tmudata' */
-size_t luaC_separateudata (lua_State *L, int all) {
-  global_State *g = G(L);
-  size_t deadmem = 0;
-  GCObject **p = &g->mainthread->next;
-  GCObject *curr;
-  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) {
-      markfinalized(gco2u(curr));  /* don't need finalization */
-      p = &curr->gch.next;
-    }
-    else {  /* must call its gc method */
-      deadmem += sizeudata(gco2u(curr));
-      markfinalized(gco2u(curr));
-      *p = curr->gch.next;
-      /* link `curr' at the end of `tmudata' list */
-      if (g->tmudata == NULL)  /* list is empty? */
-        g->tmudata = curr->gch.next = curr;  /* creates a circular list */
-      else {
-        curr->gch.next = g->tmudata->gch.next;
-        g->tmudata->gch.next = curr;
-        g->tmudata = curr;
-      }
-    }
+/*
+** mark all values stored in marked open upvalues. (See comment in
+** 'lstate.h'.)
+*/
+static void remarkupvals (global_State *g) {
+  UpVal *uv;
+  for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {
+    if (isgray(obj2gco(uv)))
+      markvalue(g, uv->v);
   }
-  return deadmem;
 }
 
 
-static int traversetable (global_State *g, Table *h) {
-  int i;
-  int weakkey = 0;
-  int weakvalue = 0;
-  const TValue *mode;
-  if (h->metatable)
-    markobject(g, h->metatable);
-  mode = gfasttm(g, h->metatable, TM_MODE);
-  if (mode && ttisstring(mode)) {  /* is there a weak mode? */
-    weakkey = (strchr(svalue(mode), 'k') != NULL);
-    weakvalue = (strchr(svalue(mode), 'v') != NULL);
-    if (weakkey || weakvalue) {  /* is really weak? */
-      h->marked &= ~(KEYWEAK | VALUEWEAK);  /* clear bits */
-      h->marked |= cast_byte((weakkey << KEYWEAKBIT) |
-                             (weakvalue << VALUEWEAKBIT));
-      h->gclist = g->weak;  /* must be cleared after GC, ... */
-      g->weak = obj2gco(h);  /* ... so put in the appropriate list */
-    }
-  }
-  if (weakkey && weakvalue) return 1;
-  if (!weakvalue) {
-    i = h->sizearray;
-    while (i--)
-      markvalue(g, &h->array[i]);
-  }
-  i = sizenode(h);
-  while (i--) {
-    Node *n = gnode(h, i);
-    lua_assert(ttype(gkey(n)) != LUA_TDEADKEY || ttisnil(gval(n)));
-    if (ttisnil(gval(n)))
-      removeentry(n);  /* remove empty entries */
+/*
+** mark root set and reset all gray lists, to start a new
+** incremental (or full) collection
+*/
+static void restartcollection (global_State *g) {
+  g->gray = g->grayagain = NULL;
+  g->weak = g->allweak = g->ephemeron = NULL;
+  markobject(g, g->mainthread);
+  markvalue(g, &g->l_registry);
+  markmt(g);
+  markbeingfnz(g);  /* mark any finalizing object left from previous cycle */
+}
+
+/* }====================================================== */
+
+
+/*
+** {======================================================
+** Traverse functions
+** =======================================================
+*/
+
+static void traverseweakvalue (global_State *g, Table *h) {
+  Node *n, *limit = gnodelast(h);
+  /* if there is array part, assume it may have white values (do not
+     traverse it just to check) */
+  int hasclears = (h->sizearray > 0);
+  for (n = gnode(h, 0); n < limit; n++) {
+    checkdeadkey(n);
+    if (ttisnil(gval(n)))  /* entry is empty? */
+      removeentry(n);  /* remove it */
     else {
       lua_assert(!ttisnil(gkey(n)));
-      if (!weakkey) markvalue(g, gkey(n));
-      if (!weakvalue) markvalue(g, gval(n));
+      markvalue(g, gkey(n));  /* mark key */
+      if (!hasclears && iscleared(g, gval(n)))  /* is there a white value? */
+        hasclears = 1;  /* table will have to be cleared */
     }
   }
-  return weakkey || weakvalue;
+  if (hasclears)
+    linktable(h, &g->weak);  /* has to be cleared later */
+  else  /* no white values */
+    linktable(h, &g->grayagain);  /* no need to clean */
 }
 
 
-/*
-** All marks are conditional because a GC may happen while the
-** prototype is still being created
-*/
-static void traverseproto (global_State *g, Proto *f) {
+static int traverseephemeron (global_State *g, Table *h) {
+  int marked = 0;  /* true if an object is marked in this traversal */
+  int hasclears = 0;  /* true if table has white keys */
+  int prop = 0;  /* true if table has entry "white-key -> white-value" */
+  Node *n, *limit = gnodelast(h);
   int i;
-  if (f->source) stringmark(f->source);
-  for (i=0; i<f->sizek; i++)  /* mark literals */
-    markvalue(g, &f->k[i]);
-  for (i=0; i<f->sizeupvalues; i++) {  /* mark upvalue names */
-    if (f->upvalues[i])
-      stringmark(f->upvalues[i]);
-  }
-  for (i=0; i<f->sizep; i++) {  /* mark nested protos */
-    if (f->p[i])
-      markobject(g, f->p[i]);
+  /* traverse array part (numeric keys are 'strong') */
+  for (i = 0; i < h->sizearray; i++) {
+    if (valiswhite(&h->array[i])) {
+      marked = 1;
+      reallymarkobject(g, gcvalue(&h->array[i]));
+    }
   }
-  for (i=0; i<f->sizelocvars; i++) {  /* mark local-variable names */
-    if (f->locvars[i].varname)
-      stringmark(f->locvars[i].varname);
+  /* traverse hash part */
+  for (n = gnode(h, 0); n < limit; n++) {
+    checkdeadkey(n);
+    if (ttisnil(gval(n)))  /* entry is empty? */
+      removeentry(n);  /* remove it */
+    else if (iscleared(g, gkey(n))) {  /* key is not marked (yet)? */
+      hasclears = 1;  /* table must be cleared */
+      if (valiswhite(gval(n)))  /* value not marked yet? */
+        prop = 1;  /* must propagate again */
+    }
+    else if (valiswhite(gval(n))) {  /* value not marked yet? */
+      marked = 1;
+      reallymarkobject(g, gcvalue(gval(n)));  /* mark it now */
+    }
   }
+  if (prop)
+    linktable(h, &g->ephemeron);  /* have to propagate again */
+  else if (hasclears)  /* does table have white keys? */
+    linktable(h, &g->allweak);  /* may have to clean white keys */
+  else  /* no white keys */
+    linktable(h, &g->grayagain);  /* no need to clean */
+  return marked;
 }
 
 
-
-static void traverseclosure (global_State *g, Closure *cl) {
-  markobject(g, cl->c.env);
-  if (cl->c.isC) {
-    int i;
-    for (i=0; i<cl->c.nupvalues; i++)  /* mark its upvalues */
-      markvalue(g, &cl->c.upvalue[i]);
+static void traversestrongtable (global_State *g, Table *h) {
+  Node *n, *limit = gnodelast(h);
+  int i;
+  for (i = 0; i < h->sizearray; i++)  /* traverse array part */
+    markvalue(g, &h->array[i]);
+  for (n = gnode(h, 0); n < limit; n++) {  /* traverse hash part */
+    checkdeadkey(n);
+    if (ttisnil(gval(n)))  /* entry is empty? */
+      removeentry(n);  /* remove it */
+    else {
+      lua_assert(!ttisnil(gkey(n)));
+      markvalue(g, gkey(n));  /* mark key */
+      markvalue(g, gval(n));  /* mark value */
+    }
   }
-  else {
-    int i;
-    lua_assert(cl->l.nupvalues == cl->l.p->nups);
-    markobject(g, cl->l.p);
-    for (i=0; i<cl->l.nupvalues; i++)  /* mark its upvalues */
-      markobject(g, cl->l.upvals[i]);
+}
+
+
+static lu_mem traversetable (global_State *g, Table *h) {
+  const char *weakkey, *weakvalue;
+  const TValue *mode = gfasttm(g, h->metatable, TM_MODE);
+  markobject(g, h->metatable);
+  if (mode && ttisstring(mode) &&  /* is there a weak mode? */
+      ((weakkey = strchr(svalue(mode), 'k')),
+       (weakvalue = strchr(svalue(mode), 'v')),
+       (weakkey || weakvalue))) {  /* is really weak? */
+    black2gray(obj2gco(h));  /* keep table gray */
+    if (!weakkey)  /* strong keys? */
+      traverseweakvalue(g, h);
+    else if (!weakvalue)  /* strong values? */
+      traverseephemeron(g, h);
+    else  /* all weak */
+      linktable(h, &g->allweak);  /* nothing to traverse now */
   }
+  else  /* not weak */
+    traversestrongtable(g, h);
+  return sizeof(Table) + sizeof(TValue) * h->sizearray +
+                         sizeof(Node) * cast(size_t, sizenode(h));
 }
 
 
-static void checkstacksizes (lua_State *L, StkId max) {
-  int ci_used = cast_int(L->ci - L->base_ci);  /* number of `ci' in use */
-  int s_used = cast_int(max - L->stack);  /* part of stack in use */
-  if (L->size_ci > LUAI_MAXCALLS)  /* handling overflow? */
-    return;  /* do not touch the stacks */
-  if (4*ci_used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci)
-    luaD_reallocCI(L, L->size_ci/2);  /* still big enough... */
-  condhardstacktests(luaD_reallocCI(L, ci_used + 1));
-  if (4*s_used < L->stacksize &&
-      2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize)
-    luaD_reallocstack(L, L->stacksize/2);  /* still big enough... */
-  condhardstacktests(luaD_reallocstack(L, s_used));
+static int traverseproto (global_State *g, Proto *f) {
+  int i;
+  if (f->cache && iswhite(obj2gco(f->cache)))
+    f->cache = NULL;  /* allow cache to be collected */
+  markobject(g, f->source);
+  for (i = 0; i < f->sizek; i++)  /* mark literals */
+    markvalue(g, &f->k[i]);
+  for (i = 0; i < f->sizeupvalues; i++)  /* mark upvalue names */
+    markobject(g, f->upvalues[i].name);
+  for (i = 0; i < f->sizep; i++)  /* mark nested protos */
+    markobject(g, f->p[i]);
+  for (i = 0; i < f->sizelocvars; i++)  /* mark local-variable names */
+    markobject(g, f->locvars[i].varname);
+  return sizeof(Proto) + sizeof(Instruction) * f->sizecode +
+                         sizeof(Proto *) * f->sizep +
+                         sizeof(TValue) * f->sizek +
+                         sizeof(int) * f->sizelineinfo +
+                         sizeof(LocVar) * f->sizelocvars +
+                         sizeof(Upvaldesc) * f->sizeupvalues;
 }
 
 
-static void traversestack (global_State *g, lua_State *l) {
-  StkId o, lim;
-  CallInfo *ci;
-  markvalue(g, gt(l));
-  lim = l->top;
-  for (ci = l->base_ci; ci <= l->ci; ci++) {
-    lua_assert(ci->top <= l->stack_last);
-    if (lim < ci->top) lim = ci->top;
-  }
-  for (o = l->stack; o < l->top; o++)
+static lu_mem traverseCclosure (global_State *g, CClosure *cl) {
+  int i;
+  for (i = 0; i < cl->nupvalues; i++)  /* mark its upvalues */
+    markvalue(g, &cl->upvalue[i]);
+  return sizeCclosure(cl->nupvalues);
+}
+
+static lu_mem traverseLclosure (global_State *g, LClosure *cl) {
+  int i;
+  markobject(g, cl->p);  /* mark its prototype */
+  for (i = 0; i < cl->nupvalues; i++)  /* mark its upvalues */
+    markobject(g, cl->upvals[i]);
+  return sizeLclosure(cl->nupvalues);
+}
+
+
+static lu_mem traversestack (global_State *g, lua_State *th) {
+  int n = 0;
+  StkId o = th->stack;
+  if (o == NULL)
+    return 1;  /* stack not completely built yet */
+  for (; o < th->top; o++)  /* mark live elements in the stack */
     markvalue(g, o);
-  for (; o <= lim; o++)
-    setnilvalue(o);
-  checkstacksizes(l, lim);
+  if (g->gcstate == GCSatomic) {  /* final traversal? */
+    StkId lim = th->stack + th->stacksize;  /* real end of stack */
+    for (; o < lim; o++)  /* clear not-marked stack slice */
+      setnilvalue(o);
+  }
+  else {  /* count call infos to compute size */
+    CallInfo *ci;
+    for (ci = &th->base_ci; ci != th->ci; ci = ci->next)
+      n++;
+  }
+  return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
+         sizeof(CallInfo) * n;
 }
 
 
 /*
-** traverse one gray object, turning it to black.
-** Returns `quantity' traversed.
+** traverse one gray object, turning it to black (except for threads,
+** which are always gray).
 */
-static l_mem propagatemark (global_State *g) {
+static void propagatemark (global_State *g) {
+  lu_mem size;
   GCObject *o = g->gray;
   lua_assert(isgray(o));
   gray2black(o);
-  switch (o->gch.tt) {
+  switch (gch(o)->tt) {
     case LUA_TTABLE: {
-      Table *h = gco2h(o);
-      g->gray = h->gclist;
-      if (traversetable(g, h))  /* table is weak? */
-        black2gray(o);  /* keep it gray */
-      return sizeof(Table) + sizeof(TValue) * h->sizearray +
-                             sizeof(Node) * sizenode(h);
-    }
-    case LUA_TFUNCTION: {
-      Closure *cl = gco2cl(o);
-      g->gray = cl->c.gclist;
-      traverseclosure(g, cl);
-      return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
-                           sizeLclosure(cl->l.nupvalues);
+      Table *h = gco2t(o);
+      g->gray = h->gclist;  /* remove from 'gray' list */
+      size = traversetable(g, h);
+      break;
+    }
+    case LUA_TLCL: {
+      LClosure *cl = gco2lcl(o);
+      g->gray = cl->gclist;  /* remove from 'gray' list */
+      size = traverseLclosure(g, cl);
+      break;
+    }
+    case LUA_TCCL: {
+      CClosure *cl = gco2ccl(o);
+      g->gray = cl->gclist;  /* remove from 'gray' list */
+      size = traverseCclosure(g, cl);
+      break;
     }
     case LUA_TTHREAD: {
       lua_State *th = gco2th(o);
-      g->gray = th->gclist;
+      g->gray = th->gclist;  /* remove from 'gray' list */
       th->gclist = g->grayagain;
-      g->grayagain = o;
+      g->grayagain = o;  /* insert into 'grayagain' list */
       black2gray(o);
-      traversestack(g, th);
-      return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
-                                 sizeof(CallInfo) * th->size_ci;
+      size = traversestack(g, th);
+      break;
     }
     case LUA_TPROTO: {
       Proto *p = gco2p(o);
-      g->gray = p->gclist;
-      traverseproto(g, p);
-      return sizeof(Proto) + sizeof(Instruction) * p->sizecode +
-                             sizeof(Proto *) * p->sizep +
-                             sizeof(TValue) * p->sizek + 
-                             sizeof(int) * p->sizelineinfo +
-                             sizeof(LocVar) * p->sizelocvars +
-                             sizeof(TString *) * p->sizeupvalues;
+      g->gray = p->gclist;  /* remove from 'gray' list */
+      size = traverseproto(g, p);
+      break;
     }
-    default: lua_assert(0); return 0;
+    default: lua_assert(0); return;
   }
+  g->GCmemtrav += size;
 }
 
 
-static size_t propagateall (global_State *g) {
-  size_t m = 0;
-  while (g->gray) m += propagatemark(g);
-  return m;
+static void propagateall (global_State *g) {
+  while (g->gray) propagatemark(g);
 }
 
 
+static void propagatelist (global_State *g, GCObject *l) {
+  lua_assert(g->gray == NULL);  /* no grays left */
+  g->gray = l;
+  propagateall(g);  /* traverse all elements from 'l' */
+}
+
 /*
-** The next function tells whether a key or value can be cleared from
-** a weak table. Non-collectable objects are never removed from weak
-** tables. Strings behave as `values', so are never removed too. for
-** other objects: if really collected, cannot keep them; for userdata
-** being finalized, keep them in keys, but not in values
+** retraverse all gray lists. Because tables may be reinserted in other
+** lists when traversed, traverse the original lists to avoid traversing
+** twice the same table (which is not wrong, but inefficient)
 */
-static int iscleared (const TValue *o, int iskey) {
-  if (!iscollectable(o)) return 0;
-  if (ttisstring(o)) {
-    stringmark(rawtsvalue(o));  /* strings are `values', so are never weak */
-    return 0;
-  }
-  return iswhite(gcvalue(o)) ||
-    (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
+static void retraversegrays (global_State *g) {
+  GCObject *weak = g->weak;  /* save original lists */
+  GCObject *grayagain = g->grayagain;
+  GCObject *ephemeron = g->ephemeron;
+  g->weak = g->grayagain = g->ephemeron = NULL;
+  propagateall(g);  /* traverse main gray list */
+  propagatelist(g, grayagain);
+  propagatelist(g, weak);
+  propagatelist(g, ephemeron);
+}
+
+
+static void convergeephemerons (global_State *g) {
+  int changed;
+  do {
+    GCObject *w;
+    GCObject *next = g->ephemeron;  /* get ephemeron list */
+    g->ephemeron = NULL;  /* tables will return to this list when traversed */
+    changed = 0;
+    while ((w = next) != NULL) {
+      next = gco2t(w)->gclist;
+      if (traverseephemeron(g, gco2t(w))) {  /* traverse marked some value? */
+        propagateall(g);  /* propagate changes */
+        changed = 1;  /* will have to revisit all ephemeron tables */
+      }
+    }
+  } while (changed);
 }
 
+/* }====================================================== */
+
 
 /*
-** clear collected entries from weaktables
+** {======================================================
+** Sweep Functions
+** =======================================================
 */
-static void cleartable (GCObject *l) {
-  while (l) {
-    Table *h = gco2h(l);
-    int i = h->sizearray;
-    lua_assert(testbit(h->marked, VALUEWEAKBIT) ||
-               testbit(h->marked, KEYWEAKBIT));
-    if (testbit(h->marked, VALUEWEAKBIT)) {
-      while (i--) {
-        TValue *o = &h->array[i];
-        if (iscleared(o, 0))  /* value was collected? */
-          setnilvalue(o);  /* remove value */
+
+
+/*
+** clear entries with unmarked keys from all weaktables in list 'l' up
+** to element 'f'
+*/
+static void clearkeys (global_State *g, GCObject *l, GCObject *f) {
+  for (; l != f; l = gco2t(l)->gclist) {
+    Table *h = gco2t(l);
+    Node *n, *limit = gnodelast(h);
+    for (n = gnode(h, 0); n < limit; n++) {
+      if (!ttisnil(gval(n)) && (iscleared(g, gkey(n)))) {
+        setnilvalue(gval(n));  /* remove value ... */
+        removeentry(n);  /* and remove entry from table */
       }
     }
-    i = sizenode(h);
-    while (i--) {
-      Node *n = gnode(h, i);
-      if (!ttisnil(gval(n)) &&  /* non-empty entry? */
-          (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
+  }
+}
+
+
+/*
+** clear entries with unmarked values from all weaktables in list 'l' up
+** to element 'f'
+*/
+static void clearvalues (global_State *g, GCObject *l, GCObject *f) {
+  for (; l != f; l = gco2t(l)->gclist) {
+    Table *h = gco2t(l);
+    Node *n, *limit = gnodelast(h);
+    int i;
+    for (i = 0; i < h->sizearray; i++) {
+      TValue *o = &h->array[i];
+      if (iscleared(g, o))  /* value was collected? */
+        setnilvalue(o);  /* remove value */
+    }
+    for (n = gnode(h, 0); n < limit; n++) {
+      if (!ttisnil(gval(n)) && iscleared(g, gval(n))) {
         setnilvalue(gval(n));  /* remove value ... */
-        removeentry(n);  /* remove entry from table */
+        removeentry(n);  /* and remove entry from table */
       }
     }
-    l = h->gclist;
   }
 }
 
 
 static void freeobj (lua_State *L, GCObject *o) {
-  switch (o->gch.tt) {
+  switch (gch(o)->tt) {
     case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break;
-    case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(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);
-      luaE_freethread(L, gco2th(o));
+    case LUA_TLCL: {
+      luaM_freemem(L, o, sizeLclosure(gco2lcl(o)->nupvalues));
       break;
     }
-    case LUA_TSTRING: {
-      G(L)->strt.nuse--;
-      luaM_freemem(L, o, sizestring(gco2ts(o)));
+    case LUA_TCCL: {
+      luaM_freemem(L, o, sizeCclosure(gco2ccl(o)->nupvalues));
       break;
     }
-    case LUA_TUSERDATA: {
-      luaM_freemem(L, o, sizeudata(gco2u(o)));
+    case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break;
+    case LUA_TTABLE: luaH_free(L, gco2t(o)); break;
+    case LUA_TTHREAD: luaE_freethread(L, gco2th(o)); break;
+    case LUA_TUSERDATA: luaM_freemem(L, o, sizeudata(gco2u(o))); break;
+    case LUA_TSHRSTR:
+      G(L)->strt.nuse--;
+      /* go through */
+    case LUA_TLNGSTR: {
+      luaM_freemem(L, o, sizestring(gco2ts(o)));
       break;
     }
     default: lua_assert(0);
@@ -400,312 +687,534 @@ static void freeobj (lua_State *L, GCObject *o) {
 }
 
 
-
 #define sweepwholelist(L,p)     sweeplist(L,p,MAX_LUMEM)
+static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count);
 
 
+/*
+** sweep the (open) upvalues of a thread and resize its stack and
+** list of call-info structures.
+*/
+static void sweepthread (lua_State *L, lua_State *L1) {
+  if (L1->stack == NULL) return;  /* stack not completely built yet */
+  sweepwholelist(L, &L1->openupval);  /* sweep open upvalues */
+  luaE_freeCI(L1);  /* free extra CallInfo slots */
+  /* should not change the stack during an emergency gc cycle */
+  if (G(L)->gckind != KGC_EMERGENCY)
+    luaD_shrinkstack(L1);
+}
+
+
+/*
+** sweep at most 'count' elements from a list of GCObjects erasing dead
+** objects, where a dead (not alive) object is one marked with the "old"
+** (non current) white and not fixed.
+** In non-generational mode, change all non-dead objects back to white,
+** preparing for next collection cycle.
+** In generational mode, keep black objects black, and also mark them as
+** old; stop when hitting an old object, as all objects after that
+** one will be old too.
+** When object is a thread, sweep its list of open upvalues too.
+*/
 static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
-  GCObject *curr;
   global_State *g = G(L);
-  int deadmask = otherwhite(g);
-  while ((curr = *p) != NULL && count-- > 0) {
-    if (curr->gch.tt == LUA_TTHREAD)  /* sweep open upvalues of each thread */
-      sweepwholelist(L, &gco2th(curr)->openupval);
-    if ((curr->gch.marked ^ WHITEBITS) & deadmask) {  /* not dead? */
-      lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT));
-      makewhite(g, curr);  /* make it white (for next cycle) */
-      p = &curr->gch.next;
-    }
-    else {  /* must erase `curr' */
-      lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
-      *p = curr->gch.next;
-      if (curr == g->rootgc)  /* is the first element of the list? */
-        g->rootgc = curr->gch.next;  /* adjust first */
-      freeobj(L, curr);
+  int ow = otherwhite(g);
+  int toclear, toset;  /* bits to clear and to set in all live objects */
+  int tostop;  /* stop sweep when this is true */
+  if (isgenerational(g)) {  /* generational mode? */
+    toclear = ~0;  /* clear nothing */
+    toset = bitmask(OLDBIT);  /* set the old bit of all surviving objects */
+    tostop = bitmask(OLDBIT);  /* do not sweep old generation */
+  }
+  else {  /* normal mode */
+    toclear = maskcolors;  /* clear all color bits + old bit */
+    toset = luaC_white(g);  /* make object white */
+    tostop = 0;  /* do not stop */
+  }
+  while (*p != NULL && count-- > 0) {
+    GCObject *curr = *p;
+    int marked = gch(curr)->marked;
+    if (isdeadm(ow, marked)) {  /* is 'curr' dead? */
+      *p = gch(curr)->next;  /* remove 'curr' from list */
+      freeobj(L, curr);  /* erase 'curr' */
+    }
+    else {
+      if (testbits(marked, tostop))
+        return NULL;  /* stop sweeping this list */
+      if (gch(curr)->tt == LUA_TTHREAD)
+        sweepthread(L, gco2th(curr));  /* sweep thread's upvalues */
+      /* update marks */
+      gch(curr)->marked = cast_byte((marked & toclear) | toset);
+      p = &gch(curr)->next;  /* go to next element */
     }
   }
+  return (*p == NULL) ? NULL : p;
+}
+
+
+/*
+** sweep a list until a live object (or end of list)
+*/
+static GCObject **sweeptolive (lua_State *L, GCObject **p, int *n) {
+  GCObject ** old = p;
+  int i = 0;
+  do {
+    i++;
+    p = sweeplist(L, p, 1);
+  } while (p == old);
+  if (n) *n += i;
   return p;
 }
 
+/* }====================================================== */
+
+
+/*
+** {======================================================
+** Finalization
+** =======================================================
+*/
 
 static void checkSizes (lua_State *L) {
   global_State *g = G(L);
-  /* check size of string hash */
-  if (g->strt.nuse < cast(lu_int32, g->strt.size/4) &&
-      g->strt.size > MINSTRTABSIZE*2)
-    luaS_resize(L, g->strt.size/2);  /* table is too big */
-  /* check size of buffer */
-  if (luaZ_sizebuffer(&g->buff) > LUA_MINBUFFER*2) {  /* buffer too big? */
-    size_t newsize = luaZ_sizebuffer(&g->buff) / 2;
-    luaZ_resizebuffer(L, &g->buff, newsize);
+  if (g->gckind != KGC_EMERGENCY) {  /* do not change sizes in emergency */
+    int hs = g->strt.size / 2;  /* half the size of the string table */
+    if (g->strt.nuse < cast(lu_int32, hs))  /* using less than that half? */
+      luaS_resize(L, hs);  /* halve its size */
+    luaZ_freebuffer(L, &g->buff);  /* free concatenation buffer */
   }
 }
 
 
-static void GCTM (lua_State *L) {
+static GCObject *udata2finalize (global_State *g) {
+  GCObject *o = g->tobefnz;  /* get first element */
+  lua_assert(isfinalized(o));
+  g->tobefnz = gch(o)->next;  /* remove it from 'tobefnz' list */
+  gch(o)->next = g->allgc;  /* return it to 'allgc' list */
+  g->allgc = o;
+  resetbit(gch(o)->marked, SEPARATED);  /* mark that it is not in 'tobefnz' */
+  lua_assert(!isold(o));  /* see MOVE OLD rule */
+  if (!keepinvariantout(g))  /* not keeping invariant? */
+    makewhite(g, o);  /* "sweep" object */
+  return o;
+}
+
+
+static void dothecall (lua_State *L, void *ud) {
+  UNUSED(ud);
+  luaD_call(L, L->top - 2, 0, 0);
+}
+
+
+static void GCTM (lua_State *L, int propagateerrors) {
   global_State *g = G(L);
-  GCObject *o = g->tmudata->gch.next;  /* get first element */
-  Udata *udata = rawgco2u(o);
   const TValue *tm;
-  /* remove udata from `tmudata' */
-  if (o == g->tmudata)  /* last element? */
-    g->tmudata = NULL;
-  else
-    g->tmudata->gch.next = udata->uv.next;
-  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) {
+  TValue v;
+  setgcovalue(L, &v, udata2finalize(g));
+  tm = luaT_gettmbyobj(L, &v, TM_GC);
+  if (tm != NULL && ttisfunction(tm)) {  /* is there a finalizer? */
+    int status;
     lu_byte oldah = L->allowhook;
-    lu_mem oldt = g->GCthreshold;
-    L->allowhook = 0;  /* stop debug hooks during GC tag method */
-    g->GCthreshold = 2*g->totalbytes;  /* avoid GC steps */
-    setobj2s(L, L->top, tm);
-    setuvalue(L, L->top+1, udata);
-    L->top += 2;
-    luaD_call(L, L->top - 2, 0);
+    int running  = g->gcrunning;
+    L->allowhook = 0;  /* stop debug hooks during GC metamethod */
+    g->gcrunning = 0;  /* avoid GC steps */
+    setobj2s(L, L->top, tm);  /* push finalizer... */
+    setobj2s(L, L->top + 1, &v);  /* ... and its argument */
+    L->top += 2;  /* and (next line) call the finalizer */
+    status = luaD_pcall(L, dothecall, NULL, savestack(L, L->top - 2), 0);
     L->allowhook = oldah;  /* restore hooks */
-    g->GCthreshold = oldt;  /* restore threshold */
+    g->gcrunning = running;  /* restore state */
+    if (status != LUA_OK && propagateerrors) {  /* error while running __gc? */
+      if (status == LUA_ERRRUN) {  /* is there an error object? */
+        const char *msg = (ttisstring(L->top - 1))
+                            ? svalue(L->top - 1)
+                            : "no message";
+        luaO_pushfstring(L, "error in __gc metamethod (%s)", msg);
+        status = LUA_ERRGCMM;  /* error in __gc metamethod */
+      }
+      luaD_throw(L, status);  /* re-throw error */
+    }
   }
 }
 
 
 /*
-** Call all GC tag methods
+** move all unreachable objects (or 'all' objects) that need
+** finalization from list 'finobj' to list 'tobefnz' (to be finalized)
 */
-void luaC_callGCTM (lua_State *L) {
-  while (G(L)->tmudata)
-    GCTM(L);
+static void separatetobefnz (lua_State *L, int all) {
+  global_State *g = G(L);
+  GCObject **p = &g->finobj;
+  GCObject *curr;
+  GCObject **lastnext = &g->tobefnz;
+  /* find last 'next' field in 'tobefnz' list (to add elements in its end) */
+  while (*lastnext != NULL)
+    lastnext = &gch(*lastnext)->next;
+  while ((curr = *p) != NULL) {  /* traverse all finalizable objects */
+    lua_assert(!isfinalized(curr));
+    lua_assert(testbit(gch(curr)->marked, SEPARATED));
+    if (!(iswhite(curr) || all))  /* not being collected? */
+      p = &gch(curr)->next;  /* don't bother with it */
+    else {
+      l_setbit(gch(curr)->marked, FINALIZEDBIT); /* won't be finalized again */
+      *p = gch(curr)->next;  /* remove 'curr' from 'finobj' list */
+      gch(curr)->next = *lastnext;  /* link at the end of 'tobefnz' list */
+      *lastnext = curr;
+      lastnext = &gch(curr)->next;
+    }
+  }
 }
 
 
-void luaC_freeall (lua_State *L) {
+/*
+** if object 'o' has a finalizer, remove it from 'allgc' list (must
+** search the list to find it) and link it in 'finobj' list.
+*/
+void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) {
   global_State *g = G(L);
-  int i;
-  g->currentwhite = WHITEBITS | bitmask(SFIXEDBIT);  /* mask to collect all elements */
-  sweepwholelist(L, &g->rootgc);
-  for (i = 0; i < g->strt.size; i++)  /* free all string lists */
-    sweepwholelist(L, &g->strt.hash[i]);
+  if (testbit(gch(o)->marked, SEPARATED) || /* obj. is already separated... */
+      isfinalized(o) ||                           /* ... or is finalized... */
+      gfasttm(g, mt, TM_GC) == NULL)                /* or has no finalizer? */
+    return;  /* nothing to be done */
+  else {  /* move 'o' to 'finobj' list */
+    GCObject **p;
+    GCheader *ho = gch(o);
+    if (g->sweepgc == &ho->next) {  /* avoid removing current sweep object */
+      lua_assert(issweepphase(g));
+      g->sweepgc = sweeptolive(L, g->sweepgc, NULL);
+    }
+    /* search for pointer pointing to 'o' */
+    for (p = &g->allgc; *p != o; p = &gch(*p)->next) { /* empty */ }
+    *p = ho->next;  /* remove 'o' from root list */
+    ho->next = g->finobj;  /* link it in list 'finobj' */
+    g->finobj = o;
+    l_setbit(ho->marked, SEPARATED);  /* mark it as such */
+    if (!keepinvariantout(g))  /* not keeping invariant? */
+      makewhite(g, o);  /* "sweep" object */
+    else
+      resetoldbit(o);  /* see MOVE OLD rule */
+  }
 }
 
+/* }====================================================== */
 
-static void markmt (global_State *g) {
-  int i;
-  for (i=0; i<NUM_TAGS; i++)
-    if (g->mt[i]) markobject(g, g->mt[i]);
+
+/*
+** {======================================================
+** GC control
+** =======================================================
+*/
+
+
+/*
+** set a reasonable "time" to wait before starting a new GC cycle;
+** cycle will start when memory use hits threshold
+*/
+static void setpause (global_State *g, l_mem estimate) {
+  l_mem debt, threshold;
+  estimate = estimate / PAUSEADJ;  /* adjust 'estimate' */
+  threshold = (g->gcpause < MAX_LMEM / estimate)  /* overflow? */
+            ? estimate * g->gcpause  /* no overflow */
+            : MAX_LMEM;  /* overflow; truncate to maximum */
+  debt = -cast(l_mem, threshold - gettotalbytes(g));
+  luaE_setdebt(g, debt);
 }
 
 
-/* mark root set */
-static void markroot (lua_State *L) {
+#define sweepphases  \
+        (bitmask(GCSsweepstring) | bitmask(GCSsweepudata) | bitmask(GCSsweep))
+
+
+/*
+** enter first sweep phase (strings) and prepare pointers for other
+** sweep phases.  The calls to 'sweeptolive' make pointers point to an
+** object inside the list (instead of to the header), so that the real
+** sweep do not need to skip objects created between "now" and the start
+** of the real sweep.
+** Returns how many objects it swept.
+*/
+static int entersweep (lua_State *L) {
   global_State *g = G(L);
-  g->gray = NULL;
-  g->grayagain = NULL;
-  g->weak = NULL;
-  markobject(g, g->mainthread);
-  /* make global table be traversed before main stack */
-  markvalue(g, gt(g->mainthread));
-  markvalue(g, registry(L));
-  markmt(g);
-  g->gcstate = GCSpropagate;
+  int n = 0;
+  g->gcstate = GCSsweepstring;
+  lua_assert(g->sweepgc == NULL && g->sweepfin == NULL);
+  /* prepare to sweep strings, finalizable objects, and regular objects */
+  g->sweepstrgc = 0;
+  g->sweepfin = sweeptolive(L, &g->finobj, &n);
+  g->sweepgc = sweeptolive(L, &g->allgc, &n);
+  return n;
 }
 
 
-static void remarkupvals (global_State *g) {
-  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);
+/*
+** change GC mode
+*/
+void luaC_changemode (lua_State *L, int mode) {
+  global_State *g = G(L);
+  if (mode == g->gckind) return;  /* nothing to change */
+  if (mode == KGC_GEN) {  /* change to generational mode */
+    /* make sure gray lists are consistent */
+    luaC_runtilstate(L, bitmask(GCSpropagate));
+    g->GCestimate = gettotalbytes(g);
+    g->gckind = KGC_GEN;
+  }
+  else {  /* change to incremental mode */
+    /* sweep all objects to turn them back to white
+       (as white has not changed, nothing extra will be collected) */
+    g->gckind = KGC_NORMAL;
+    entersweep(L);
+    luaC_runtilstate(L, ~sweepphases);
   }
 }
 
 
-static void atomic (lua_State *L) {
+/*
+** call all pending finalizers
+*/
+static void callallpendingfinalizers (lua_State *L, int propagateerrors) {
   global_State *g = G(L);
-  size_t udsize;  /* total size of userdata to be finalized */
-  /* remark occasional upvalues of (maybe) dead threads */
-  remarkupvals(g);
-  /* traverse objects cautch by write barrier and by 'remarkupvals' */
-  propagateall(g);
-  /* remark weak tables */
-  g->gray = g->weak;
-  g->weak = NULL;
+  while (g->tobefnz) {
+    resetoldbit(g->tobefnz);
+    GCTM(L, propagateerrors);
+  }
+}
+
+
+void luaC_freeallobjects (lua_State *L) {
+  global_State *g = G(L);
+  int i;
+  separatetobefnz(L, 1);  /* separate all objects with finalizers */
+  lua_assert(g->finobj == NULL);
+  callallpendingfinalizers(L, 0);
+  g->currentwhite = WHITEBITS; /* this "white" makes all objects look dead */
+  g->gckind = KGC_NORMAL;
+  sweepwholelist(L, &g->finobj);  /* finalizers can create objs. in 'finobj' */
+  sweepwholelist(L, &g->allgc);
+  for (i = 0; i < g->strt.size; i++)  /* free all string lists */
+    sweepwholelist(L, &g->strt.hash[i]);
+  lua_assert(g->strt.nuse == 0);
+}
+
+
+static l_mem atomic (lua_State *L) {
+  global_State *g = G(L);
+  l_mem work = -cast(l_mem, g->GCmemtrav);  /* start counting work */
+  GCObject *origweak, *origall;
   lua_assert(!iswhite(obj2gco(g->mainthread)));
   markobject(g, L);  /* mark running thread */
-  markmt(g);  /* mark basic metatables (again) */
-  propagateall(g);
-  /* remark gray again */
-  g->gray = g->grayagain;
-  g->grayagain = NULL;
-  propagateall(g);
-  udsize = luaC_separateudata(L, 0);  /* separate userdata to be finalized */
-  marktmu(g);  /* mark `preserved' userdata */
-  udsize += propagateall(g);  /* remark, to propagate `preserveness' */
-  cleartable(g->weak);  /* remove collected objects from weak tables */
-  /* flip current white */
-  g->currentwhite = cast_byte(otherwhite(g));
-  g->sweepstrgc = 0;
-  g->sweepgc = &g->rootgc;
-  g->gcstate = GCSsweepstring;
-  g->estimate = g->totalbytes - udsize;  /* first estimate */
+  /* registry and global metatables may be changed by API */
+  markvalue(g, &g->l_registry);
+  markmt(g);  /* mark basic metatables */
+  /* remark occasional upvalues of (maybe) dead threads */
+  remarkupvals(g);
+  propagateall(g);  /* propagate changes */
+  work += g->GCmemtrav;  /* stop counting (do not (re)count grays) */
+  /* traverse objects caught by write barrier and by 'remarkupvals' */
+  retraversegrays(g);
+  work -= g->GCmemtrav;  /* restart counting */
+  convergeephemerons(g);
+  /* at this point, all strongly accessible objects are marked. */
+  /* clear values from weak tables, before checking finalizers */
+  clearvalues(g, g->weak, NULL);
+  clearvalues(g, g->allweak, NULL);
+  origweak = g->weak; origall = g->allweak;
+  work += g->GCmemtrav;  /* stop counting (objects being finalized) */
+  separatetobefnz(L, 0);  /* separate objects to be finalized */
+  markbeingfnz(g);  /* mark objects that will be finalized */
+  propagateall(g);  /* remark, to propagate `preserveness' */
+  work -= g->GCmemtrav;  /* restart counting */
+  convergeephemerons(g);
+  /* at this point, all resurrected objects are marked. */
+  /* remove dead objects from weak tables */
+  clearkeys(g, g->ephemeron, NULL);  /* clear keys from all ephemeron tables */
+  clearkeys(g, g->allweak, NULL);  /* clear keys from all allweak tables */
+  /* clear values from resurrected weak tables */
+  clearvalues(g, g->weak, origweak);
+  clearvalues(g, g->allweak, origall);
+  g->currentwhite = cast_byte(otherwhite(g));  /* flip current white */
+  work += g->GCmemtrav;  /* complete counting */
+  return work;  /* estimate of memory marked by 'atomic' */
 }
 
 
-static l_mem singlestep (lua_State *L) {
+static lu_mem singlestep (lua_State *L) {
   global_State *g = G(L);
-  /*lua_checkmemory(L);*/
   switch (g->gcstate) {
     case GCSpause: {
-      markroot(L);  /* start a new collection */
-      return 0;
+      /* start to count memory traversed */
+      g->GCmemtrav = g->strt.size * sizeof(GCObject*);
+      lua_assert(!isgenerational(g));
+      restartcollection(g);
+      g->gcstate = GCSpropagate;
+      return g->GCmemtrav;
     }
     case GCSpropagate: {
-      if (g->gray)
-        return propagatemark(g);
+      if (g->gray) {
+        lu_mem oldtrav = g->GCmemtrav;
+        propagatemark(g);
+        return g->GCmemtrav - oldtrav;  /* memory traversed in this step */
+      }
       else {  /* no more `gray' objects */
-        atomic(L);  /* finish mark phase */
-        return 0;
+        lu_mem work;
+        int sw;
+        g->gcstate = GCSatomic;  /* finish mark phase */
+        g->GCestimate = g->GCmemtrav;  /* save what was counted */;
+        work = atomic(L);  /* add what was traversed by 'atomic' */
+        g->GCestimate += work;  /* estimate of total memory traversed */ 
+        sw = entersweep(L);
+        return work + sw * GCSWEEPCOST;
       }
     }
     case GCSsweepstring: {
-      lu_mem old = g->totalbytes;
-      sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]);
-      if (g->sweepstrgc >= g->strt.size)  /* nothing more to sweep? */
-        g->gcstate = GCSsweep;  /* end sweep-string phase */
-      lua_assert(old >= g->totalbytes);
-      g->estimate -= old - g->totalbytes;
-      return GCSWEEPCOST;
+      int i;
+      for (i = 0; i < GCSWEEPMAX && g->sweepstrgc + i < g->strt.size; i++)
+        sweepwholelist(L, &g->strt.hash[g->sweepstrgc + i]);
+      g->sweepstrgc += i;
+      if (g->sweepstrgc >= g->strt.size)  /* no more strings to sweep? */
+        g->gcstate = GCSsweepudata;
+      return i * GCSWEEPCOST;
     }
-    case GCSsweep: {
-      lu_mem old = g->totalbytes;
-      g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
-      if (*g->sweepgc == NULL) {  /* nothing more to sweep? */
-        checkSizes(L);
-        g->gcstate = GCSfinalize;  /* end sweep phase */
-      }
-      lua_assert(old >= g->totalbytes);
-      g->estimate -= old - g->totalbytes;
-      return GCSWEEPMAX*GCSWEEPCOST;
-    }
-    case GCSfinalize: {
-      if (g->tmudata) {
-        GCTM(L);
-        if (g->estimate > GCFINALIZECOST)
-          g->estimate -= GCFINALIZECOST;
-        return GCFINALIZECOST;
+    case GCSsweepudata: {
+      if (g->sweepfin) {
+        g->sweepfin = sweeplist(L, g->sweepfin, GCSWEEPMAX);
+        return GCSWEEPMAX*GCSWEEPCOST;
       }
       else {
-        g->gcstate = GCSpause;  /* end collection */
-        g->gcdept = 0;
+        g->gcstate = GCSsweep;
         return 0;
       }
     }
+    case GCSsweep: {
+      if (g->sweepgc) {
+        g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
+        return GCSWEEPMAX*GCSWEEPCOST;
+      }
+      else {
+        /* sweep main thread */
+        GCObject *mt = obj2gco(g->mainthread);
+        sweeplist(L, &mt, 1);
+        checkSizes(L);
+        g->gcstate = GCSpause;  /* finish collection */
+        return GCSWEEPCOST;
+      }
+    }
     default: lua_assert(0); return 0;
   }
 }
 
 
-void luaC_step (lua_State *L) {
+/*
+** advances the garbage collector until it reaches a state allowed
+** by 'statemask'
+*/
+void luaC_runtilstate (lua_State *L, int statesmask) {
   global_State *g = G(L);
-  l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
-  if (lim == 0)
-    lim = (MAX_LUMEM-1)/2;  /* no limit */
-  g->gcdept += g->totalbytes - g->GCthreshold;
-  do {
-    lim -= singlestep(L);
-    if (g->gcstate == GCSpause)
-      break;
-  } while (lim > 0);
-  if (g->gcstate != GCSpause) {
-    if (g->gcdept < GCSTEPSIZE)
-      g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
-    else {
-      g->gcdept -= GCSTEPSIZE;
-      g->GCthreshold = g->totalbytes;
-    }
-  }
-  else {
-    lua_assert(g->totalbytes >= g->estimate);
-    setthreshold(g);
-  }
+  while (!testbit(statesmask, g->gcstate))
+    singlestep(L);
 }
 
 
-void luaC_fullgc (lua_State *L) {
+static void generationalcollection (lua_State *L) {
   global_State *g = G(L);
-  if (g->gcstate <= GCSpropagate) {
-    /* reset sweep marks to sweep all elements (returning them to white) */
-    g->sweepstrgc = 0;
-    g->sweepgc = &g->rootgc;
-    /* reset other collector lists */
-    g->gray = NULL;
-    g->grayagain = NULL;
-    g->weak = NULL;
-    g->gcstate = GCSsweepstring;
-  }
-  lua_assert(g->gcstate != GCSpause && g->gcstate != GCSpropagate);
-  /* finish any pending sweep phase */
-  while (g->gcstate != GCSfinalize) {
-    lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep);
-    singlestep(L);
+  lua_assert(g->gcstate == GCSpropagate);
+  if (g->GCestimate == 0) {  /* signal for another major collection? */
+    luaC_fullgc(L, 0);  /* perform a full regular collection */
+    g->GCestimate = gettotalbytes(g);  /* update control */
   }
-  markroot(L);
-  while (g->gcstate != GCSpause) {
-    singlestep(L);
+  else {
+    lu_mem estimate = g->GCestimate;
+    luaC_runtilstate(L, bitmask(GCSpause));  /* run complete (minor) cycle */
+    g->gcstate = GCSpropagate;  /* skip restart */
+    if (gettotalbytes(g) > (estimate / 100) * g->gcmajorinc)
+      g->GCestimate = 0;  /* signal for a major collection */
+    else
+      g->GCestimate = estimate;  /* keep estimate from last major coll. */
+
   }
-  setthreshold(g);
+  setpause(g, gettotalbytes(g));
+  lua_assert(g->gcstate == GCSpropagate);
 }
 
 
-void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
+static void incstep (lua_State *L) {
   global_State *g = G(L);
-  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
-  lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
-  lua_assert(ttype(&o->gch) != LUA_TTABLE);
-  /* must keep invariant? */
-  if (g->gcstate == GCSpropagate)
-    reallymarkobject(g, v);  /* restore invariant */
-  else  /* don't mind */
-    makewhite(g, o);  /* mark as white just to avoid other barriers */
+  l_mem debt = g->GCdebt;
+  int stepmul = g->gcstepmul;
+  if (stepmul < 40) stepmul = 40;  /* avoid ridiculous low values (and 0) */
+  /* convert debt from Kb to 'work units' (avoid zero debt and overflows) */
+  debt = (debt / STEPMULADJ) + 1;
+  debt = (debt < MAX_LMEM / stepmul) ? debt * stepmul : MAX_LMEM;
+  do {  /* always perform at least one single step */
+    lu_mem work = singlestep(L);  /* do some work */
+    debt -= work;
+  } while (debt > -GCSTEPSIZE && g->gcstate != GCSpause);
+  if (g->gcstate == GCSpause)
+    setpause(g, g->GCestimate);  /* pause until next cycle */
+  else {
+    debt = (debt / stepmul) * STEPMULADJ;  /* convert 'work units' to Kb */
+    luaE_setdebt(g, debt);
+  }
 }
 
 
-void luaC_barrierback (lua_State *L, Table *t) {
+/*
+** performs a basic GC step
+*/
+void luaC_forcestep (lua_State *L) {
   global_State *g = G(L);
-  GCObject *o = obj2gco(t);
-  lua_assert(isblack(o) && !isdead(g, o));
-  lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
-  black2gray(o);  /* make table gray (again) */
-  t->gclist = g->grayagain;
-  g->grayagain = o;
+  int i;
+  if (isgenerational(g)) generationalcollection(L);
+  else incstep(L);
+  /* run a few finalizers (or all of them at the end of a collect cycle) */
+  for (i = 0; g->tobefnz && (i < GCFINALIZENUM || g->gcstate == GCSpause); i++)
+    GCTM(L, 1);  /* call one finalizer */
 }
 
 
-void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
+/*
+** performs a basic GC step only if collector is running
+*/
+void luaC_step (lua_State *L) {
   global_State *g = G(L);
-  o->gch.next = g->rootgc;
-  g->rootgc = o;
-  o->gch.marked = luaC_white(g);
-  o->gch.tt = tt;
+  if (g->gcrunning) luaC_forcestep(L);
+  else luaE_setdebt(g, -GCSTEPSIZE);  /* avoid being called too often */
 }
 
 
-void luaC_linkupval (lua_State *L, UpVal *uv) {
+
+/*
+** performs a full GC cycle; if "isemergency", does not call
+** finalizers (which could change stack positions)
+*/
+void luaC_fullgc (lua_State *L, int isemergency) {
   global_State *g = G(L);
-  GCObject *o = obj2gco(uv);
-  o->gch.next = g->rootgc;  /* link upvalue into `rootgc' list */
-  g->rootgc = o;
-  if (isgray(o)) { 
-    if (g->gcstate == GCSpropagate) {
-      gray2black(o);  /* closed upvalues need barrier */
-      luaC_barrier(L, uv, uv->v);
-    }
-    else {  /* sweep phase: sweep it (turning it into white) */
-      makewhite(g, o);
-      lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
-    }
+  int origkind = g->gckind;
+  lua_assert(origkind != KGC_EMERGENCY);
+  if (isemergency)  /* do not run finalizers during emergency GC */
+    g->gckind = KGC_EMERGENCY;
+  else {
+    g->gckind = KGC_NORMAL;
+    callallpendingfinalizers(L, 1);
+  }
+  if (keepinvariant(g)) {  /* may there be some black objects? */
+    /* must sweep all objects to turn them back to white
+       (as white has not changed, nothing will be collected) */
+    entersweep(L);
+  }
+  /* finish any pending sweep phase to start a new cycle */
+  luaC_runtilstate(L, bitmask(GCSpause));
+  luaC_runtilstate(L, ~bitmask(GCSpause));  /* start new collection */
+  luaC_runtilstate(L, bitmask(GCSpause));  /* run entire collection */
+  if (origkind == KGC_GEN) {  /* generational mode? */
+    /* generational mode must be kept in propagate phase */
+    luaC_runtilstate(L, bitmask(GCSpropagate));
   }
+  g->gckind = origkind;
+  setpause(g, gettotalbytes(g));
+  if (!isemergency)   /* do not run finalizers during emergency GC */
+    callallpendingfinalizers(L, 1);
 }
 
+/* }====================================================== */
+
+