标记-清除(mark-sweep)算法
Emacs Lisp最早使用的就是标记清除算法. 算法分为"标记"和"清除"两个阶段.
1) 首先标记出所有正在使用的对象.
2) 回收那些所有未被标记的对象,并清除掉标记.
该算法的缺点是:
1) 效率问题, 标记和清除的效率并不高.
2) GC运行时, 正常程序必须停下来, 降低实时性.
下面以elisp中的cons单元的为例来释放标记-清除的算法.
elisp中的所有对象是 lisp_object.
typedef lisp_object {
unsigned int val;
unsigned int type:7;
unsigned int mark:1;
} lisp_object;
其实lisp_object是个联合体(union), 这里只描述lisp_object中的GC相关的部分.
type : 表示该lisp_object的类型, 有符号,函数,cons,或者字符串等等.
val : 表示该lisp_object的值, 一般来说是相应类型的指针.
mark : mark-sweep算法中使用, 表示该对象是否被标记. 未被标记的对象代表着不会被引用到,要回收.
cons的结构体相对比较简单点,就包含car和cdr两个对象.
struct lisp_cons {
lisp_ojbect car, cdr;
};
了解了cons和lisp_object对象结构之后, 我们还需要知道cons的内存申请,标记和回收.
一. cons的内存申请步骤:
1)查看空闲的cons链表, 为了节省空间把car当做链表指针. 如果不为空的话,则直接从空闲链表中取出一个cons单元
2)如果空闲链表为空, 则从cons块中申请一个cons单元. 一个cons块有500个cons单元, 每个块形成一个链表.
cons函数实现如下:
lisp_object Fcons(lisp_object car, libp_object cdr) {
lisp_object val;
if (cons_free_list) {
// 设置lisp_object的类型为cons, 值为cons_free_list的指针
XSET(val, Lisp_Cons, cons_free_list);
// cons_free_list 指向链表的下一个地址
cons_free_list = (struct Lisp_Cons *) XFASTINT (cons_free_list->car);
} else {
// cons_block_index 为cons块使用的索引, cons_block为当前正在使用的cons块
if (cons_block_index == CONS_BLOCK_SIZE) {
struct cons_block *new = (struct cons_block *) malloc (sizeof (struct cons_block));
if (!new) memory_full ();
new->next = cons_block;
cons_block = new;
cons_block_index = 0;
}
XSET (val, Lisp_Cons, &cons_block->conses[cons_block_index++]);
}
XCONS (val)->car = car;
XCONS (val)->cdr = cdr;
return val;
}
二. cons块的标记. lisp的GC要标记出所有可达的对象, 就必须记录那些全局的对象.根据全局对象对其他对象的引用链来标记出所有的引用对象, 这样那些申请的,而没被标记出的对象就是可回收的. 下面来看一下标记函数如何来标记cons对象的.
void mark_object(lisp_object *objptr) {
switch (XGCTYPE (obj))
case Lisp_Cons : {
struct Lisp_Cons *ptr = XCONS (obj);
if (XMARKBIT (ptr->car)) break;
XMARK (ptr->car);
mark_object(&ptr->car);
mark_object (&ptr->cdr);
break;
/* other object */
case ....:
break;
}
}
三. 标记出所有cons的可达对象之后,就需要扫描所有的被申请的cons对象, 并把那些未标记的cons对象添加的cons空闲链表中.
void sweep_cons(void) {
struct cons_block *cblk;
int lim = cons_block_index;
int num_free = 0, num_used = 0;
cons_free_list = 0;
// 扫描所有的空闲块
for (cblk = cons_block; cblk; cblk = cblk->next) {
int i;
// 扫描空闲块中的所有cons单元, 查看其是否被标记
for (i = 0; i < lim; i++) {
if (!XMARKBIT (cblk->conses[i].car)) {
XFASTINT (cblk->conses[i].car) = (int) cons_free_list;
num_free++;
cons_free_list = &cblk->conses[i];
} else {
num_used++;
XUNMARK (cblk->conses[i].car);
}
}
lim = CONS_BLOCK_SIZE;
}
// 统计使用和未使用的cons单元数量
total_conses = num_used;
total_free_conses = num_free;
}
至于elisp其他类型的对象也依此类推, 不过是标记的地方不一样了而已. 总体来说标记-清除算法还是比较简单的, 不过越是简单的东西越是基础, 掌握的这个算法之后我们就可以进阶其他的改进GC算法了.
本文参考了Emacs-18.59的代码, 旧版本的Emacs代码可以从这个网站上下载: ftp://ftp.gnu.org/old-gnu/emacs/.
之所以选择旧版本代码阅读, 是因为旧版本的代码比较少,功能简单, 核心思想却于新版本差不多.