首页 > 代码库 > Lua1.1 垃圾回收
Lua1.1 垃圾回收
垃圾回收
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/
Lua1.1 垃圾回收