用 C 语言编写一个简单的垃圾回收器

人们似乎觉得编写垃圾回收机制是非常难的，是一种仅仅有少数智者和Hans Boehm(et al)才干理解的高深魔法。我觉得编写垃圾回收最难的地方就是内存分配，这和阅读K&R所写的malloc例子难度是相当的。

在開始之前有一些重要的事情须要说明一下：第一。我们所写的代码是基于Linux Kernel的。注意是Linux Kernel而不是GNU/Linux。第二，我们的代码是32bit的。第三。请不要直接使用这些代码。我并不保证这些代码全然正确，可能当中有一些我还未发现的小的bug，可是总体思路仍然是正确的。好了。让我们開始吧。

假设你看到不论什么有误的地方，请邮件联系我maplant2@illinois.edu

编写malloc

最開始，我们须要写一个内存分配器(memmory allocator)，也能够叫做内存分配函数(malloc function)。最简单的内存分配实现方法就是维护一个由空暇内存块组成的链表。这些空暇内存块在须要的时候被切割或分配。

当用户请求一块内存时。一块合适大小的内存块就会从链表中被移除并分配给用户。假设链表中没有合适的空暇内存块存在，并且更大的空暇内存块已经被切割成小的内存块了或内核也正在请求很多其它的内存(译者注：就是链表中的空暇内存块都太小不足以分配给用户的情况)。

那么此时。会释放掉一块内存并把它加入到空暇块链表中。

在链表中的每一个空暇内存块都有一个头(header)用来描写叙述内存块的信息。

我们的header包括两个部分，第一部分表示内存块的大小，第二部分指向下一个空暇内存块。

1 2 3 4

typedef struct header{     unsigned int  size;     struct block  *next; } header_t;

将头(header)内嵌进内存块中是唯一明智的做法。并且这样还能够享有字节自己主动对齐的优点，这非常重要。

因为我们须要同一时候跟踪我们“当前使用过的内存块”和“未使用的内存块”，因此除了维护空暇内存的链表外，我们还须要一条维护当前已用内存块的链表(为了方便。这两条链表后面分别写为“空暇块链表”和“已用块链表”)。我们从空暇块链表中移除的内存块会被加入到已用块链表中。反之亦然。

如今我们差点儿相同已经做好准备来完毕malloc实现的第一步了。

可是再那之前，我们须要知道如何向内核申请内存。

动态分配的内存会驻留在一个叫做堆(heap)的地方。堆是介于栈(stack)和BSS(未初始化的数据段－你全部的全局变量都存放在这里且具有默认值为0)之间的一块内存。堆(heap)的内存地址起始于(低地址)BSS段的边界，结束于一个分隔地址(这个分隔地址是已建立映射的内存和未建立映射的内存的分隔线)。为了可以从内核中获取很多其它的内存，我们仅仅需提高这个分隔地址。为了提高这个分隔地址我们须要调用一个叫作 sbrk 的Unix系统的系统调用，这个函数可以依据我们提供的參数来提高分隔地址，假设函数运行成功则会返回曾经的分隔地址。假设失败将会返回－1。

利用我们如今知道的知识，我们能够创建两个函数：morecore()和add_to_free_list()。当空暇块链表缺少内存块时，我们调用morecore()函数来申请很多其它的内存。因为每次向内核申请内存的代价是昂贵的，我们以页(page-size)为单位申请内存。页的大小在这并非非常重要的知识点，只是这有一个非常easy解释：页是虚拟内存映射到物理内存的最小内存单位。接下来我们就能够使用add_to_list()将申请到的内存块增加空暇块链表。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

/*  * Scan the free list and look for a place to put the block. Basically, we're  * looking for any block the to be freed block might have been partitioned from.  */ static void add_to_free_list(header_t *bp) {     header_t *p;       for (p = freep; !(bp > p && bp < p->next); p = p->next)         if (p >= p->next && (bp > p || bp < p->next))             break;       if (bp + bp->size == p->next) {         bp->size += p->next->size;         bp->next = p->next->next;     } else         bp->next = p->next;       if (p + p->size == bp) {         p->size += bp->size;         p->next = bp->next;     } else         p->next = bp;       freep = p; }   #define MIN_ALLOC_SIZE 4096 /* We allocate blocks in page sized chunks. */   /*  * Request more memory from the kernel.  */ static header_t * morecore(size_t num_units) {     void *vp;     header_t *up;       if (num_units < MIN_ALLOC_SIZE)         num_units = MIN_ALLOC_SIZE / sizeof(header_t);       if ((vp = sbrk(num_units * sizeof(header_t))) == (void *) -1)         return NULL;                   up = (header_t *) vp;     up->size = num_units;     add_to_free_list (up);     return freep; }

如今我们有了两个有力的函数，接下来我们就能够直接编写malloc函数了。

我们扫描空暇块链表当遇到第一块满足要求的内存块(内存块比所需内存大即满足要求)时。停止扫描，而不是扫描整个链表来寻找大小最合适的内存块，我们所採用的这样的算法思想事实上就是首次适应(与最佳适应相对)。

注意：有件事情须要说明一下。内存块头部结构中size这一部分的计数单位是块(Block)，而不是Byte。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

static header_t base; /* Zero sized block to get us started. */ static header_t *usedp, *freep;   /*  * Find a chunk from the free list and put it in the used list.  */ void * GC_malloc(size_t alloc_size) {     size_t num_units;     header_t *p, *prevp;       num_units = (alloc_size + sizeof(header_t) - 1) / sizeof(header_t) + 1;      prevp = freep;       for (p = prevp->next;; prevp = p, p = p->next) {         if (p->size >= num_units) { /* Big enough. */             if (p->size == num_units) /* Exact size. */                 prevp->next = p->next;             else {                 p->size -= num_units;                 p += p->size;                 p->size = num_units;             }               freep = prevp;                           /* Add to p to the used list. */             if (usedp == NULL)                  usedp = p->next = p;             else {                 p->next = usedp->next;                 usedp->next = p;             }               return (void *) (p + 1);         }         if (p == freep) { /* Not enough memory. */             p = morecore(num_units);             if (p == NULL) /* Request for more memory failed. */                 return NULL;         }     } }

注意这个函数的成功与否，取决于我们第一次使用时是否使 freep = &base 。

这点我们会在初始化函数中进行设置。

虽然我们的代码全然没有考虑到内存碎片，可是它能工作。既然它能够工作。我们就能够開始下一个有趣的部分－垃圾回收！

标记和清扫

我们说过垃圾回收器会非常easy，因此我们尽可能的使用简单的方法：标记和清除方式。这个算法分为两个部分：

首先，我们须要扫描全部可能存在指向堆中数据(heap data)的变量的内存空间并确认这些内存空间中的变量是否指向堆中的数据。为了做到这点。对于可能内存空间中的每一个字长(word-size)的数据块，我们遍历已用块链表中的内存块。假设数据块所指向的内存是在已用链表块中的某一内存块中，我们对这个内存块进行标记。

第二部分是，当扫描全然部可能的内存空间后。我们遍历已用块链表将全部未被标记的内存块移到空暇块链表中。

如今非常多人会開始觉得仅仅是靠编写类似于malloc那样的简单函数来实现C的垃圾回收是不可行的，由于在函数中我们无法获得其外面的非常多信息。比如，在C语言中没有函数能够返回分配到堆栈中的全部变量的哈希映射。

可是仅仅要我们意识到两个重要的事实，我们就能够绕过这些东西：

第一，在C中，你能够尝试訪问不论什么你想訪问的内存地址。由于不可能有一个数据块编译器能够訪问可是其地址却不能被表示成一个能够赋值给指针的整数。假设一块内存在C程序中被使用了。那么它一定能够被这个程序訪问。这是一个令不熟悉C的编程者非常困惑的概念，由于非常多编程语言都会限制程序訪问虚拟内存，可是C不会。

第二。全部的变量都存储在内存的某个地方。这意味着假设我们能够知道变量们的通常存储位置，我们能够遍历这些内存位置来寻找每一个变量的全部可能值。另外。由于内存的訪问一般是字(word-size)对齐的，因此我们仅须要遍历内存区域中的每一个字(word)就可以。

局部变量也能够被存储在寄存器中，可是我们并不须要操心这些由于寄存器常常会用于存储局部变量。并且当函数被调用的时候他们一般会被存储在堆栈中。

如今我们有一个标记阶段的策略：遍历一系列的内存区域并查看是否有内存可能指向已用块链表。

编写这种一个函数很的简洁明了：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#define UNTAG(p) (((unsigned int) (p)) & 0xfffffffc)   /*  * Scan a region of memory and mark any items in the used list appropriately.  * Both arguments should be word aligned.  */ static void mark_from_region(unsigned int *sp, unsigned int *end) {     header_t *bp;       for (; sp < end; sp++) {         unsigned int v = *sp;         bp = usedp;         do {             if (bp + 1 <= v &&                 bp + 1 + bp->size > v) {                     bp->next = ((unsigned int) bp->next) | 1;                     break;             }         } while ((bp = UNTAG(bp->next)) != usedp);     } }

为了确保我们仅仅使用头(header)中的两个字长(two words)我们使用一种叫做标记指针(tagged pointer)的技术。利用header中的next指针指向的地址总是字对齐(word aligned)这一特点，我们能够得出指针低位的几个有效位总会是0。因此我们将next指针的最低位进行标记来表示当前块是否被标记。

如今，我们能够扫描内存区域了。可是我们应该扫描哪些内存区域呢？我们要扫描的有下面这些：

1. BBS(未初始化数据段)和初始化数据段。这里包括了程序的全局变量和局部变量。由于他们有可能应用堆(heap)中的一些东西，所以我们须要扫描BSS与初始化数据段。

2. 已用的数据块。当然。假设用户分配一个指针来指向还有一个已经被分配的内存块。我们不会想去释放掉那个被指向的内存块。
3. 堆栈。

   由于堆栈中包括全部的局部变量。因此这能够说是最须要扫描的区域了。

我们已经了解了关于堆(heap)的一切，因此编写一个mark_from_heap函数将会很easy：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

/*  * Scan the marked blocks for references to other unmarked blocks.  */ static void mark_from_heap(void) {     unsigned int *vp;     header_t *bp, *up;       for (bp = UNTAG(usedp->next); bp != usedp; bp = UNTAG(bp->next)) {         if (!((unsigned int)bp->next & 1))             continue;         for (vp = (unsigned int *)(bp + 1);              vp < (bp + bp->size + 1);              vp++) {             unsigned int v = *vp;             up = UNTAG(bp->next);             do {                 if (up != bp &&                     up + 1 <= v &&                     up + 1 + up->size > v) {                     up->next = ((unsigned int) up->next) | 1;                     break;                 }             } while ((up = UNTAG(up->next)) != bp);         }     } }

幸运的是对于BSS段和已初始化数据段，大部分的现代unix链接器能够导出 etext 和 end 符号。etext符号的地址是初始化数据段的起点(the last address past the text segment，这个段中包括了程序的机器码)。end符号是堆(heap)的起点。因此，BSS和已初始化数据段位于 &etext 与 &end 之间。

这种方法足够简单，当不是平台独立的。

堆栈这部分有一点困难。堆栈的栈顶很easy找到。仅仅须要使用一点内联汇编就可以，由于它存储在 sp 这个寄存器中。可是我们将会使用的是 bp 这个寄存器。由于它忽略了一些局部变量。

寻找堆栈的的栈底(堆栈的起点)涉及到一些技巧。

出于安全因素的考虑，内核倾向于将堆栈的起点随机化，因此我们非常难得到一个地址。老实说，我在寻找栈底方面并非专家。可是我有一些点子能够帮你找到一个准确的地址。一个可能的方法是，你能够扫描调用栈(call stack)来寻找 env 指针。这个指针会被作为一个參数传递给主程序。还有一种方法是从栈顶開始读取每一个更大的兴许地址并处理inexorible SIGSEGV。可是我们并不打算採用这两种方法中的不论什么一种，我们将利用linux会将栈底放入一个字符串并存于proc文件夹下表示该进程的文件里这一事实。

这听起来非常愚蠢并且非常间接。值得庆幸的是，我并不感觉这样做是滑稽的，由于它和Boehm GC中寻找栈底所用的方法全然同样。

如今我们能够编写一个简单的初始化函数。在函数中。我们打开proc文件并找到栈底。

栈底是文件里第28个值，因此我们忽略前27个值。Boehm GC和我们的做法不同的是他仅使用系统调用来读取文件来避免让stdlib库使用堆(heap)，可是我们并不在意这些。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

/*  * Find the absolute bottom of the stack and set stuff up.  */ void GC_init(void) {     static int initted;     FILE *statfp;       if (initted)         return;       initted = 1;       statfp = fopen("/proc/self/stat", "r");     assert(statfp != NULL);     fscanf(statfp,            "%*d %*s %*c %*d %*d %*d %*d %*d %*u "            "%*lu %*lu %*lu %*lu %*lu %*lu %*ld %*ld "            "%*ld %*ld %*ld %*ld %*llu %*lu %*ld "            "%*lu %*lu %*lu %lu", &stack_bottom);     fclose(statfp);       usedp = NULL;     base.next = freep = &base;     base.size = 0;

如今我们知道了每一个我们须要扫描的内存区域的位置。所以我们最终能够编写显示调用的回收函数了：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

/*  * Mark blocks of memory in use and free the ones not in use.  */ void GC_collect(void) {     header_t *p, *prevp, *tp;     unsigned long stack_top;     extern char end, etext; /* Provided by the linker. */       if (usedp == NULL)         return;           /* Scan the BSS and initialized data segments. */     mark_from_region(&etext, &end);       /* Scan the stack. */     asm volatile ("movl    %%ebp, %0" : "=r" (stack_top));     mark_from_region(stack_top, stack_bottom);       /* Mark from the heap. */     mark_from_heap();       /* And now we collect! */     for (prevp = usedp, p = UNTAG(usedp->next);; prevp = p, p = UNTAG(p->next)) {     next_chunk:         if (!((unsigned int)p->next & 1)) {             /*              * The chunk hasn't been marked. Thus, it must be set free.              */             tp = p;             p = UNTAG(p->next);             add_to_free_list(tp);               if (usedp == tp) {                 usedp = NULL;                 break;             }               prevp->next = (unsigned int)p | ((unsigned int) prevp->next & 1);             goto next_chunk;         }         p->next = ((unsigned int) p->next) & ~1;         if (p == usedp)             break;     } }

朋友们，全部的东西都已经在这了。一个用C为C程序编写的垃圾回收器。这些代码自身并非完整的。它还须要一些微调来使它能够正常工作，可是大部分代码是能够独立工作的。

总结

从小学到高中，我一直在学习打鼓。每一个星期三的下午4:30左右我都会更一个非常棒的老师上打鼓教学课。

每当我在学习一些新的打槽（groove）或节拍时，我的老师总会给我一个同样的告诫：我试图同一时候做所有的事情。我看着乐谱，我仅仅是简单地尝试用双手将它所有演奏出来。可是我做不到。

原因是由于我还不知道如何打槽，但我却在学习打槽地时候同一时候学习其他东西而不是单纯地练习打槽。

因此我的老师教导我该怎样去学习：不要想着能够同一时候做全部地事情。先学习用你地右手打架子鼓，当你学会之后，再学习用你的左手打小鼓。用相同地方式学习贝斯、手鼓和其他部分。当你能够单独使用每一个部分之后，慢慢開始同一时候练习它们，先两个同一时候练习，然后三个。最后你将能够能够同一时候完毕全部部分。

我在打鼓方面从来都不够优秀。但我在编程时始终记着这门课地教训。

一開始就打算编写完整的程序是非常困难的，你编程的唯一算法就是分而治之。先编写内存分配函数。然后编写查询内存的函数，然后是清除内存的函数。最后将它们合在一起。

当你在编程方面克服这个障碍后，就再也没有困难的实践了。

你可能有一个算法不太了解，可是不论什么人仅仅要有足够的时间就肯定能够通过论文或书理解这个算法。假设有一个项目看起来令人生畏，那么将它分成全然独立的几个部分。

你可能不懂怎样编写一个解释器。但你绝对能够编写一个分析器，然后看一下你还有什么须要加入的。添上它。