Emergency Garbage Collector

wiki

This page is about creating an emergency garbage collector patch for Lua 5.1.4. Please note that LuaFiveTwo has an emergency garbage collector listed as one of the features that will be included. Work on this patch is being done separately from the emergency garbage collector that might be included in LuaFiveTwo.

The Emergency GC patch makes it safe to call the Lua garbage collector after a memory allocation has failed. This allows the garbage collector to free some memory so that the failed allocation can be retried. The patch also add support for setting a limit on how much memory Lua scripts can allocate.

Files

[Download emergency gc patch for (5.1.4) release 6]

[Program for stress-testing the emergency garbage collection.]

Extra memory optimization features.

These are included in the Emergency GC patch. They can be used without the emergency gc patch.

Resizing of the internal strings hashtable requires an extra hashtable to be allocated. For scripts that need to run with a very small amount of memory (64-256kbytes), this can cause "not enough memory" errors when the script is low on memory(only 1-2kbytes free). I have an idea on how to resize the hashtable in place without the extra hashtable. The one downside is that some strings in the hashtable will be removed & added multiple times. So this method will use more CPU time to save some extra memory use. [Stringtable patch for 5.1.3]
The hashpart of Lua tables has the same resize problem that the strings hashtable has. Resizing the hashpart of tables will require more work, since the resize code is more complex. [Hashpart patch for 5.1.3]

Notes about how the Lua garbage collector works

Disclaimer: This is the first time I have worked on a garbage collector so some of this may be incorrect. Corrections/cleanups are welcome. --RobertGabrielJakabosky

"While working on this patch I had to learn how the garbage collector in Lua works. I am writing this to help me later if I need to fix more bugs with the collector and I hope this info can help other people who are interested in how the Lua garbage collector works." --RobertGabrielJakabosky

Simple description

The Lua garbage collector is a mark & sweep collector. The collector has two major phases mark & sweep that it runs each collection cycle. During the mark phases the collector traverse the Lua stack and into tables to mark values it finds as live. Next the sweep phases will walk a list of all collectible values and free all dead values it finds.

Detailed description

All collectible type objects have a 'marked' bit field. The bits are defined as (copied from header "lgc.h"):

bit 0 - object is white (type 0)
bit 1 - object is white (type 1)
bit 2 - object is black
bit 3 - for userdata: has been finalized
bit 3 - for tables: has weak keys (note this bit has two different meanings one for userdata and one for tables)
bit 4 - for tables: has weak values
bit 5 - object is fixed (should not be collected)
bit 6 - object is "super" fixed (only the main thread)

The garbage collector keeps track of a current white (type 0 or 1) and objects with the other white are dead objects that can be collected during the sweep states.

An object's color is defined by which of the first 3 bits (0, 1, 2) are set:

It is white if one of the two white bits (0,1) are set and the black bit is clear. Only one white bit should be used by a white object.
It is gray if all three color bits (0,1,2) are clear.
It is black if the black bit is set and the two white bits are clear.

Garbage collector states (each collection cycle passes through these states in this order):

GCSpause - Start of collection cycle. At this state all objects should be marked with the current white. The main lua_State, globals table, registry, and metatables are marked gray and added to the gray list. The state now changes to GCSpropagate.
GCSpropagate - Each object in the gray list is removed and marked black, then any white (type 0 or 1) objects it references are marked gray and added to the gray list. Once the gray list is empty the current white is switched to the other white. All objects marked with the old white type are now dead objects. The state now changes to GCSsweepstring.
GCSsweepstring - The color of each string in the internal strings hashtable is checked. If the color matches the old white type that string is dead and is freed. If the color matches the current white (newly created string) or is gray (some other object references it), then it is alive and its color is reset to the current white. Once all strings are checked the state is changed to GCSsweep.
GCSsweep - The color of each objects in the global rootgc list (this list holds all objects except strings) is checked just like the strings during the GCSsweepstring state. Dead objects are freed and removed from the rootgc list. Live objects have their color reset to the current white. Once all objects have been checked the state is changed to GCSfinalize.
GCSfinalize - This state will finalize all dead userdata objects by running their "__gc" metamethod. Once all dead userdata objects have been finailzed the state is changed to GCSpause and this completes a cycle of the garbage collector.