本文主要是介绍Writing a Simple Garbage Collector in C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 制作malloc
- 标记与扫描
- 扫描堆
- 扫描连续区域
- 查找数据段
- 查找调用堆栈底部
- 整合
用 C 语言编写一个简单的垃圾回收器 (maplant.com)
制作malloc
标头描述内存块
typedef struct header {unsigned int size;struct header *next;
} header_t;
动态分配的内存位于所谓的堆中，这是堆栈和BSS(未初始化的数据段—所有默认值为零的全局变量)之间的一段内存。堆从与BSS相邻的低地址开始，并在程序断点处结束，程序断点位于BSS和堆栈之间的某个地方。
程序间断点就是程序数据段的结尾。（程序间断点是为初始化数据段的起始位置）
试图访问堆栈和断点之间的任何内存都会导致访问冲突（除非您访问的内存在堆栈可以扩展的范围内，但这是一个完全不同的话题）。
为了从内核中获得更多的内存，我们只需延长断点，从而允许我们访问更多的内存。为此，我们调用Unix的sbrk系统调用，它通过参数扩展break，并在成功时返回前一个break的地址，从而为程序提供更多的内存。失败时，sbrk返回被强制转换为空指针的-1，这是一个没有人喜欢的糟糕约定。
- 栈区（stack）：由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
- 堆区（heap） ：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
一个可执行程序在存储时（没有加载到内存运行），至少拥有三个部分，分别是代码段(text)、数据段(data)、和BSS 段。当应用程序运行时（运行态），此时需要另外两个域：堆和栈。正在运行的程序：代码段 + 数据段 + BSS 段 + 堆 + 栈。
static header_t base; /* 零大小的块开始. */
static header_t *freep = &base; /* 指向第一个空闲内存块. ？*/
static header_t *usedp; /*指向第一个使用的内存块. *//** 扫描空闲列表并寻找放置块的地方。基本上，我们要查找的是即将被释放的块可能已经被分区的任何块。*/
static void
add_to_free_list(header_t *bp)
{header_t *p;//查找bp是否在freep范围内//for循环判断条件：p < bp < p->next 在中间//if条件：bp < p->next < p < bp 在两边（freep是循环的？）for (p = freep; !(bp > p && bp < p->next); p = p->next)if (p >= p->next && (bp > p || bp < p->next))break;//满足两个条件中其一...//如果bp和p->next相邻（bp < p->next）：if (bp + bp->size == p->next) {//两者的头信息合并（覆盖）bp->size += p->next->size;bp->next = p->next->next;} else//不相邻就赋nextbp->next = p->next;//如果p和bp相邻（p < bp）：if (p + p->size == bp) {//合并p->size += bp->size;p->next = bp->next;} elsep->next = bp;//freep可能是循环的freep = p;
}
sbrk()参数函数中：当increment为正值时，间断点位置向后移动increment字节。同时返回移动之前的位置，相当于分配内存。当increment为负值时，位置向前移动increment字节，相当与于释放内存，其返回值没有实际意义。当increment为0时，不移动位置只返回当前位置。参数increment的符号决定了是分配还是回收内存。
#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);//先除再乘sizeof(header_t)是为了将num_units化为MIN_ALLOC_SIZE的整数倍//vp是新申请的内存的头指针if ((vp = sbrk(num_units * sizeof(header_t))) == (void *) -1)return NULL;//强转成header_t，存储头信息up = (header_t *) vp;up->size = num_units;//将新申请的内存加入freepadd_to_free_list (up);return freep;
}
现在我们有了两个辅助函数，编写malloc函数就非常简单了。我们只需扫描空闲列表，并使用至少与我们要查找的块一样大的第一个块。因为我们使用我们找到的第一个块，而不是试图找到一个“更好”的块，这个算法被称为首次拟合（First Fit）。
快速说明一下:header结构体中的size字段是以header大小的块为单位测量的，而不是字节。
/** 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;//这里 alloc_size + sizeof(header_t) 是整个内存块结构（字节）//之所以-1是为了让被除数不能被sizeof(header_t)整除，从而+1，获取向上取整的内存块以header_t大小为单位的大小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移动到分配的内存的头部p->size = num_units;//设置大小}//preve保存着剩下的内存块的头信息freep = prevp;/* Add to p to the used list. */if (usedp == NULL) usedp = p->next = p;else {//插入usedp链p->next = usedp->next;usedp->next = p;}//p+1是为了跳过sizeof(header_t)个字节，直接获取有效内存的地址return (void *) (p + 1);}if (p == freep) { /* Not enough memory. */p = morecore(num_units);//向内核申请更多的内存if (p == NULL) /* Request for more memory failed. */return NULL;}//到这里还没有分配，但是已经调用morecore()且成功获取内存了，所以循环，看看申请来的内存是否够分配}
}
标记与扫描
遍历一个区间的内存，然后
//解标记，这里解标记是把低两位置0，但是标记位只有最后一位 ？
#define UNTAG(p) (((unsigned int) (p)) & 0xfffffffc)/** 扫描内存区域，并在已使用列表中适当地标记任何项目。* 两个参数都应该对齐。*/
static void
scan_region(unsigned int *sp, unsigned int *end)
{header_t *bp;for (; sp < end; sp++) {unsigned int v = *sp;bp = usedp;do {//v在bp的有效内存地址内if (bp + 1 <= v &&bp + 1 + bp->size > v) {//将 bp->next 的第一位置1，进行标记bp->next = ((unsigned int) bp->next) | 1;break;}//循环直到再次遇见usedp，所以可能usedp也是循环的} while ((bp = UNTAG(bp->next)) != usedp);}
}
现在我们可以扫描内存区域了，但是我们应该浏览哪些内存区域呢?有几个相关区域:
- BSS(未初始化的数据)和初始化的数据段:它们包含程序中的所有全局变量和静态变量。因此，它们可以引用堆中的某些内容。
- 使用的块:当然，如果用户分配一个指向另一个已分配块的指针，我们不希望释放指向的块。
- 堆栈:由于堆栈包含所有的局部变量，因此可以说这是最重要的地方。
扫描堆
/** Scan the marked blocks for references to other unmarked blocks.*/
static void
scan_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))//是否有标记，没有则continuecontinue;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) {//v在up的有效内存地址内up->next = ((unsigned int) up->next) | 1;break;}} while ((up = UNTAG(up->next)) != bp);}}
}
扫描连续区域
与堆不同，BSS 和初始化的数据段以及堆栈都是 内存中可能包含堆中的地址。因为每个都是连续的，所以为了扫描它们，我们需要知道每个最小有效和最大有效内存地址。
查找数据段
初始化数据段和BSS相邻
大多数现代 Unix 链接器导出两个符号，可供用户程序访问，这些符号是 我们感兴趣的是：
- etext：etext的地址是文本段之后的最后一个地址。初始化的数据 段紧跟在文本段之后，因此 etext 的地址是初始化的数据段。
- end：end 的地址是堆的开头，或者是 BSS 末尾之后的最后一个地址。
由于 BSS 和初始化段之间没有段，因此我们不必处理它们 作为单独的实体，可以通过从 &etext 迭代到 & end 来扫描它们。
直接使用extern char end, etext;即可获取到
查找调用堆栈底部
堆栈顶部可用内联汇编取出esp寄存器值来获取。堆栈底部我们将利用Linux将堆栈底部放在proc目录中进程条目的文件中的字符串中的事实
整合
/** 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);//取第28个数据，所以前27个忽略（"%*lu"）fclose(statfp);usedp = NULL;base.next = freep = &base;base.size = 0;
}
/** 标记已使用的内存块并释放未使用的内存块*/
void
GC_collect(void)
{header_t *p, *prevp, *tp;unsigned long stack_top;extern char end, etext; /* 链接器提供. */if (usedp == NULL)return;/* 扫描BSS和初始化的数据段. */scan_region(&etext, &end);/* 扫描栈. */asm volatile ("movl %%ebp, %0" : "=r" (stack_top));scan_region(stack_top, stack_bottom);/* 标记堆. */scan_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)) {/** 这部分还没有标记。因此，它必须被释放 */tp = p;p = UNTAG(p->next);add_to_free_list(tp);if (usedp == tp) { usedp = NULL;break;}//先做((unsigned int) prevp->next & 1，取出prevp->next的标志位，然后加到pprevp->next = (unsigned int)p | ((unsigned int) prevp->next & 1);goto next_chunk;}//将p->next的标志位清零p->next = ((unsigned int) p->next) & ~1;if (p == usedp)break;}
}
这篇关于Writing a Simple Garbage Collector in C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
