GC之Mark&Sweep

[Hazlank]

动态存储器

为什么会有动态存储器？在很多情况下，只有在程序运行时才能知道数据结构大小，在静态编译过程申请的内存往往可能并不够用,所以我们需要显示的给程序申请分配内存。

动态存储分配器维护着一个进程的虚拟存储器区域，称为堆(heap)，分配器将堆视为一组不同大小的块(block)的集合来维护，要么是已分配，要么就是空闲的。已分配块显示的保留为应用程序使用。空闲块可以用来分配。一个空闲块块保持空闲状态直到被应用分配。已分配块也是保持分配状态直到被释放，这种分配释放要么是应用显式调用api执行，要么就是存储器自身隐式执行。

分配器有两种风格。两种风格都要求应用显式分配块。不同之处在于由哪个实体来负责释放已分配块

• 显示分配器
  要求应用显式释放任何已分配的块。C标准库提供malloc程序包的显式分配器，它能够调用malloc来分配块，并调用free函数释放一个块。它相当于C++的new和delete操作符
• 隐式分配器
  另一方面，要求分配器检测已分配块什么时候不再被程序使用时，就释放这个块。隐式分配器也叫做垃圾回收器(garbage collect)，自动释放未使用的已分配块就叫垃圾回收(garbage collection).

malloc和free

#include <stdlib.h>

void *malloc(size_t, size)
void free(void *ptr)

malloc返回一个指针，指向大小至少为size字节的存储器块。free的ptr参数必须指向一个从malloc，calloc或realloc获得的已分配块的起始位置。

垃圾回收

垃圾回收可以追溯到20世纪60代John McCarthy开发的LISP语言，它是诸如Java,ML,Perl等现代语言系统的重要一部分。McCarthy也创造了Mark&Sweep（标记&清除）,它可以建立在malloc包的基础之上，为c和c++程序提供垃圾回收

垃圾收集器

垃圾收集器将存储器视为一张有向可达图，它分为一组根节点和一组堆节点,每个堆节点对应一个已分配的块

在任何时刻，不可达节点对应着垃圾，是不能被应用再次使用，应该被回收。垃圾回收器的角色是维护可达图的某种表示，并通过释放不可达节点将他们返回给空闲链表，来定期回收他们。收集器可以按需提供他们的服务，或者作为一个和应用并行的独立线程，不断更新可达图和回收垃圾。

无论何时需要堆空间，应用都会用通常的方式调用malloc。如果malloc找不到一个合适的空闲块，那么它就会调用垃圾收集器，希望回收一些垃圾到空闲链表，再通过调用free函数返回给堆。关键的思想是收集器代替应用去调用free。

Mark&Sweep垃圾收集器

Mark&Sweep垃圾收集器由标记和清除阶段组成，标记阶段标记出根节点所有可达和已分配的后继，而后面的清除阶段释放每个未标记的已分配块。典型的，我们可以用块头部空闲的低位中的一位用来表示这个块是否被标记。

当然前面也没讲过是怎么分配块的，所以会不清楚块的结构。往往分配器需要一些数据结构来区分块边界,以及区分已分配块和空闲块，大多数分配器会把这些信息嵌入块本身。所以一个数据块不单单只有有效载荷（数据)它还维护着其他信息，比如块大小，块的头部脚部信息链接上下其他块以做合并空闲块，或者在空闲的高位或低位做标识符，是否允许程序可读可写数据。

mark和sweep伪代码

/*
ptr isPtr(ptr p): 如果p指向一个已分配块中的某个字，就返回一个指向这个块起始位置的指针b
int blockMarked(ptr b): 如果标记了块b，就返回true
int blockAlllocated(ptr b): 如果块b是已分配就返回true
void markBlock(ptr b): 标记块b
void unmarkBlock(ptr b): 将块b由已标记改为未标记
ptr nextBlock(ptr b): 返回块b的后继
*/

void mark(ptr p) {
	if ((b = isPtr(p)) == NULL)
		return;
	if(blockMarked(b))
		return;
	markBlock(b);
	len = length(b);
	for(i=0;i<len;i++)
		mark(b[i])
	return;
}

void sweep(ptr b, ptr end){
	while(b<end) {
		if(blockMarked(b))
			unmarkBlock(b);
		else if (blockAllocated(b))
			free(b)
		b = nextBlock(b);
	}
	return;
}

mark函数指针p如果不指向一个分配并且未标记的块就会返回。否则就标记块，并且对块中的字递归调用它自己，标记可达的后继节点，在标记末尾，任何未被标记的块都视为垃圾，可以收回
sweep函数在堆里每个块反复循环并且释放所有未标记的块