"Simple" generational GC

[Mark Hamburg <mhamburg@...>]

Caveat: The following is based on my general understanding of how the Lua GC
works as opposed to a detailed inspection and effort.

As I understand it, Lua maintains a list of all live or possibly live
objects. When using threads, presumably this list lives in the root state,
but I haven't checked.

Considering segregating this list into two parts. Per state we would keep a
nursery list reflecting every object created in that state and not known to
be promoted to the global list. We would also keep a global list. If not
using threads or coroutines, this amounts to two lists.

Every object keeps a flag indicating whether or not it is a nursery object.
The invariant we maintain is that nursery objects can only be reached from
the state they were created in or via other nursery objects for that state.
When a store would violate this condition, we clear the nursery flag. The
only things that I can think of that would clear the nursery flag include:

* table stores where the table doesn't have the nursery flag set
* stores to upvalues where the function doesn't have the nursery flag set
* lua_xmove
* setting the metatable on tables and userdata that don't have the nursery
flag set

That seems like a reasonably small list of places to test.

Given this, we can now do a "nursery collection" for a Lua state. We clear
the mark flags for any objects in the nursery (if they aren't kept in the
cleared state). We then use the state as the root for marking items with the
additional property that we don't need to follow any paths leading through
non-nursery objects. We can then scan the nursery list and collect anything
that isn't marked. At this time, we can also move any objects that have
ceased to be nursery objects to the global object list.

The only other complication I can think of that this adds to the GC is that
a global collection will need to be aware of the nursery lists in its scan
phase. This could also have the effect of breaking the GC order guarantees
for userdata, but those guarantees could probably be modified slightly to
reflect the new behavior -- e.g., something like saying the order is
preserved amongst items created in the same state.

For people more familiar with the Lua GC, does this seem like a reasonable
scheme?

Mark