垃圾回收
Lua1.1 中使用的是标记清理算法（Mark-and-sweep）。
Lua1.1 中有两种对象会被垃圾回收，字符串 string 和数组 array。
先看一下和垃圾回收相关的两个变量：
/* Variables to controll garbage collection */ Word lua_block=10; /* to check when garbage collector will be called */ Word lua_nentity; /* counter of new entities (strings and arrays) */
lua_nentity 是需要垃圾回收对象的计数器。
lua_block 是当垃圾回收对象计数达到它时进行垃圾回收。
垃圾回收算法入口：
table.c
/*
** Garbage collection.
** Delete all unused strings and arrays.
*/
void lua_pack (void)
{
/* mark stack strings */
lua_travstack(lua_markobject);
/* mark symbol table strings */
lua_travsymbol(lua_markobject);
lua_stringcollector();
lua_hashcollector();
lua_nentity = 0; /* reset counter */
}
标记栈中正在使用的字符串和数组。
标记符号表中的正在使用的字符串和数组。
回收字符串。
回收数组。
垃圾回收结束后，重置 lua_nentity。
先看一下什么时候会调用到这个垃圾回收算法
char *lua_createstring (char *s)
{
/*other codes*/
if (lua_nentity == lua_block || lua_nstring >= MAXSTRING-1)
{
lua_pack ();
/*other codes*/
}
/*other codes*/
lua_nentity++;
return s;
}
这是一处，新建字符串时当垃圾回收对象数达到了 lua_block （lua_nentity == lua_block）
字符串达到了最大个数（ lua_nstring >= MAXSTRING-1）。
Hash *lua_createarray (int nhash)
{
/*other codes*/
if (lua_nentity == lua_block)
lua_pack();
lua_nentity++;
/*other codes*/
}
这是另一处，新建数组时，当垃圾回收对象数达到了 lua_block （lua_nentity == lua_block）时。
可以看到在上面的 lua_createstring 和 lua_createarray 中有 lua_nentity 的自加运算来计数。
在 lua_travstack 和 lua_travsymbol 中都会用到函数 lua_markobject。
table.c
/*
** Mark an object if it is a string or a unmarked array.
*/
void lua_markobject (Object *o)
{
if (tag(o) == T_STRING)
markstring (svalue(o)) = 1;
else if (tag(o) == T_ARRAY)
lua_hashmark (avalue(o));
}
可以看到，标记 Object 时只标记 T_STRING 型和 T_ARRAY 型。
markstring 时就是把 string 的第一位置位，在 Lua1.1 里，string 保存的时候是从实际空间的第二位开始的，第一位空着就是为了垃圾回收里做标记用的。
lua_hashmark 时是个递归调用，把数组本身标记后，再在数组里的所有键值对上分别调用 lua_markobject。
opcode.c
/*
** Traverse all objects on stack
*/
void lua_travstack (void (*fn)(Object *))
{
Object *o;
for (o = top-1; o >= stack; o--)
fn (o);
}
遍历栈，调用 lua_markobject 标记栈中的 Object.
table.c
/*
** Traverse symbol table objects
*/
void lua_travsymbol (void (*fn)(Object *))
{
int i;
for (i=0; i<lua_ntable; i++)
fn(&s_object(i));
}
遍历符号表，调用 lua_markobject 标记其中的 Object.
table.c
/*
** Garbage collection to atrings.
** Delete all unmarked strings
*/
void lua_stringcollector (void)
{
int i, j;
for (i=j=0; i<lua_nstring; i++)
if (markstring(lua_string[i]) == 1)
{
lua_string[j++] = lua_string[i];
markstring(lua_string[i]) = 0;
}
else
{
free (lua_string[i]-1);
}
lua_nstring = j;
}
字符串垃圾回收，清除所有的未使用的字符串（就是没有标记上的），释放相应内存，调整字符串在字符串表中的位置，重置字符串标记，最后调整字符串表的大小。
hash.c
/*
** Garbage collection to arrays
** Delete all unmarked arrays.
*/
void lua_hashcollector (void)
{
ArrayList *curr = listhead, *prev = NULL;
while (curr != NULL)
{
ArrayList *next = curr->next;
if (markarray(curr->array) != 1)
{
if (prev == NULL) listhead = next;
else prev->next = next;
hashdelete(curr->array);
free(curr);
}
else
{
markarray(curr->array) = 0;
prev = curr;
}
curr = next;
}
}
数组垃圾回收，清除所有的未使用的数组（就是没有标记上的）和数组里的结点，从数组链表里去掉未标记的数组，释放相应内存，重置数组的标记。
可以看出，这个垃圾回收算法在执行的时候，应用程序是不能运行其它任务的（其它的非垃圾回复的任务），
这也就是所谓的停止世界（Stop the world)。 不过后来，Lua 采用的就是增量垃圾回收算法。
对简单的标记清除垃圾回收算法感兴趣的还可以看看下面这篇：
http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/
它的中文翻译：blog.jobbole.com/53376/
原文：http://my.oschina.net/xhan/blog/314059