Writing a Mark-Sweep Garbage Collector
Tracing vs. Direct collectors
所有 GC 算法都分为tracing和direct。
尽管被称为“垃圾”收集器，但跟踪收集器实际上并不识别垃圾。相反，情况恰恰相反——它们识别活着的对象，通过扩展将其他一切视为垃圾。
Mark-Sweep 是一个跟踪收集器，因此我们将在我们的实现中进行跟踪阶段。
由于我们选择在 C++ 中实现收集器，我们现在将讨论与它的运行时系统相关的一些细节。
C++ specifics
下面是一些与 C++ 运行时相关的细节，它们会影响我们的实现。
Exposed pointers semantics
正如我们之前讨论的讨论的那样，C++ 将指针语义暴露给用户级。这意味着，我们可以获得一个指向对象的指针，并将其作为可观察值存储在某个变量中。
这反过来使得在 C++ 运行时实现移动（如 Mark-Compact）或复制（Generational、Semi-Space 收集器）变得更加困难：如果我们重新定位一个对象，所有指针都将失效，并且包含不正确的地址。
对于 Java、JavaScript 和其他不直接在用户代码中使用原始内存的语言，它要简单得多，还有许多其他选项。
幸运的是，Mark-Sweep 是一个非移动收集器，这意味着我们可以用 C++ 实现它，这是一项非常有趣的工程任务，因为我们需要接触堆栈、寄存器、一些汇编的概念，以及其他的东西。
Pointer or number?
为了实现跟踪算法，我们应该能够获得对象形状内的所有（子）指针。然后跟随子指针，再次获取它们的指针，等等——遍历整个对象图。
然而，一旦我们在 C++ 中获得了一个指针，通常我们无法判断它是否真的是一个指针，或者只是一个简单的数字——回想一下，垃圾收集器在只有字节的较低级别工作，但不是实际的具体 C++结构。
同样，托管高级语言，例如 Java、JS 等，会跟踪值类型，并且可以轻松区分指针和其他值。为此，此类语言使用不同类型的值编码，其中最流行的是标记指针和NaN 装箱。编码总是假设解码的逆操作，这通常发生在运行时。它可能会减慢操作速度，但它是实现大多数动态编程语言的事实上的标准。
在 C++ 中，而不是编码值（并在运行时不断解码它们），我们将使用带有“鸭子测试”的保守方法——如果它看起来像一个指针，并且真的指向一个已知的堆地址，那么它必须是一个指针，我们需要跟踪它。毫不奇怪，这些收藏家被称为保守派。
GC roots
垃圾收集器根对象（或简称根）为出发点，从我们开始我们的跟踪分析。这些对象保证是存活的，因为通常由堆栈上的全局或局部变量指向。
更高级别的虚拟机可能会出于 GC 的目的跟踪所有根，从而使诸如此类的过程getRoots更加简单。但是在 C++ 中，我们必须手动遍历堆栈，保守地收集根。
此外，一些局部变量可能会放在 CPU 寄存器中，我们也必须遍历它们。幸运的是，我们可以使用一种将所有寄存器压入堆栈的技巧，这将为我们节省一些时间和实现工作。
好的，现在让我们直接进入实现，从对象图开始。
Implementation
我们将在这个实现中使用自顶向下的方法，从高级和基本概念开始，将 C++ 的具体细节留到最后。
Traceable objects
我们实现的关键部分将是Traceable对象，它将跟踪垃圾收集器所需的所有信息。稍后我们将描述Traceable结构体的细节，现在让我们展示如何创建简单地继承它的结构体：
我们实现的关键部分将是Traceable对象，它将跟踪垃圾收集器所需的所有信息。稍后我们将描述Traceable结构体的细节，现在让我们展示如何创建简单地继承它的结构体：
/**
* Traceable Node structure.
*
* Contains the name of the node, and the
* pointers to left and right sub-nodes,
* forming a tree.
*/
struct Node : public Traceable {
char name;
Node *left;
Node *right;
};
所有可追踪对象都可以访问所谓的Object header，其中包含 GC 元信息。让我们看看它是什么。
Object header
顾名思义，Mark-Sweep 收集器由两个阶段组成：标记阶段（活动对象的跟踪）和清除阶段（垃圾回收）。要将对象标记为活动的，收集器需要将此标志存储在某处，这就是对象头发挥作用的地方。
我们的头将包含两个字段：标记位和对象的大小：
/**
* Object header.
*/
struct ObjectHeader {
bool marked;
size_t size;
};
每个可跟踪对象都可以访问其标头（通过基Traceable类）：
// Create a node:
auto node = new Node {.name = 'A'};
// Obtain the header:
auto header = node->getHeader();
std::cout << header->marked; // false
std::cout << header->size; // 24
用户代码通常不需要（也不应该）访问标头元信息，这主要是针对 GC 本身的。但是，我们在此将其公开为用于教育目的的公共方法。
好的，现在当我们有能力创建具有可追溯元信息的对象时，让我们创建我们的工作图。
Object graph
这是对象图的示例，我们将在进一步分析中使用它：
/*
Graph:
A -- Root
/ \
B C
/ \
D E
/ \
F G
\
H
*/
Node *createGraph() {
auto H = new Node{.name = 'H'};
auto G = new Node{.name = 'G', .right = H};
auto F = new Node{.name = 'F'};
auto E = new Node{.name = 'E', .left = F, .right = G};
auto D = new Node{.name = 'D'};
auto C = new Node{.name = 'C', .left = D, .right = E};
auto B = new Node{.name = 'B'};
auto A = new Node{.name = 'A', .left = B, .right = C};
return A; // Root
}
然后我们在我们的main函数中创建这个对象图，只有对象A作为根：
int main(int argc, char const *argv[]) {
gcInit(); // (1)
auto A = createGraph(); // (2)
// Full alive graph:
dump("Allocated graph:"); // (3)
...
return 0;
}
注意在（1）中我们如何调用gcInit()函数——在任何与可追踪对象分配相关的操作之前。我们稍后会讨论这个函数，现在让我们看一下我们在（2）中创建的图：
所以它是一棵树，由节点创建，每个节点都有左右两侧。目前我们看到，只有变量A被保证是一个已知的可达引用。总的来说，我们对 的子节点一无所知A——因为它们都没有被变量指向。
在（3）中，我们转储分配的堆，它向我们展示了每个对象的地址和对象头：
------------------------------------------------
Allocated graph:
{
[H] 0x7fed26401770: {.marked = 0, .size = 24},
[G] 0x7fed264017d0: {.marked = 0, .size = 24},
[F] 0x7fed26401830: {.marked = 0, .size = 24},
[E] 0x7fed26401890: {.marked = 0, .size = 24},
[D] 0x7fed264018f0: {.marked = 0, .size = 24},
[C] 0x7fed26401950: {.marked = 0, .size = 24},
[B] 0x7fed264019b0: {.marked = 0, .size = 24},
[A] 0x7fed26401a10: {.marked = 0, .size = 24},
}
正如我们所见，它们都没有被标记，因为还没有执行 GC 循环。此外，它们都不是垃圾。
我们现在将讨论这些垃圾如何出现在我们的记忆中。
The garbage
“垃圾”如何出现在我们的记忆中，“垃圾”到底是什么？
从跟踪收集器的角度来看，垃圾是一个无法访问的对象。这基本上意味着在跟踪阶段没有访问对象。
注意：与分析对象引用次数的引用计数收集器相反，跟踪收集器使用可达性的概念：一个对象可能仍然有对它的引用，但同时是一个无法访问的垃圾。
让我们看看它的实际效果：
// Detach the whole right sub-tree:
A->right = nullptr;
这个单一的操作基本上变成了一个垃圾对象的整个右子树A。轻微修正：是垃圾回收系统中的垃圾；在纯 C++ 中，这实际上是内存泄漏。
显然，此时只有左子树是可达的，其他一切都是垃圾：
现在是深入了解实现的好时机，看看我们程序的GC 循环内部发生了什么。
在这里，我们将使用特定的 C++ 功能，覆盖new运算符的默认行为。就其本身而言，此运算符是默认malloc分配器之上的瘦包装器。我们的实现也将是一个瘦包装器，它为我们的数据初始化对象头。
这是在Traceable我们上面讨论的基类中完成的：
/**
* The `Traceable` struct is used as a base class
* for any object which should be managed by GC.
*/
struct Traceable {
ObjectHeader *getHeader() { return traceInfo.at(this); }
static void *operator new(size_t size) {
// Allocate a block:
void *object = ::operator new(size);
// Create an object header for it:
auto header = new ObjectHeader{.marked = false, .size = size};
traceInfo.insert(std::make_pair((Traceable *)object, header));
// Result is the actual block:
return object;
}
};
这里我们分配对象头，并将其存储在额外的traceInfo数据结构中，该数据结构是从分配的指针到其头的映射。
注意：可以选择将对象头与有效负载指针位于同一位置。
最后让我们来看看实际的收集算法。
Mark phase
让我们main再次从我们函数的代码开始，看看我们是如何调用 GC 循环的：
int main(int argc, char const *argv[]) {
gcInit();
auto A = createGraph();
// Full alive graph:
dump("Allocated graph:");
// Detach the whole right sub-tree:
A->right = nullptr;
// Run GC:
gc();
return 0;
}
我们的gc函数也很简单——调用mark阶段，然后是sweep阶段：
/**
* Mark-Sweep GC.
*/
void gc() {
mark();
dump("After mark:");
sweep();
dump("After sweep:");
}
在每一步之后，我们转储堆以查看数据如何更改。让我们从mark阶段开始，看看结果。
如果您听过视频讲座，那么您应该已经熟悉以下代码：
/**
* Mark phase.
*/
void mark() {
auto worklist = getRoots();
while (!worklist.empty()) {
auto o = worklist.back();
worklist.pop_back();
auto header = o->getHeader();
if (!header->marked) {
header->marked = true;
for (const auto &p : getPointers(o)) {
worklist.push_back(p);
}
}
}
}
重申一下，我们从根开始分析，初始化worklist. 遍历此工作列表中的每个对象，我们将其标记为活动的，然后更深入地查看子指针，也将它们添加到工作列表中。
到此操作结束时，整个访问过的图将被标记为活动的。未访问的对象最终将被回收为垃圾。为此，我们需要实现上面使用的getRoots和getPointers函数。
遍历之后，我们的图如下所示：
以及我们的内存转储中反映的内容：
------------------------------------------------
After mark:
{
[H] 0x7fed26401770: {.marked = 0, .size = 24},
[G] 0x7fed264017d0: {.marked = 0, .size = 24},
[F] 0x7fed26401830: {.marked = 0, .size = 24},
[E] 0x7fed26401890: {.marked = 0, .size = 24},
[D] 0x7fed264018f0: {.marked = 0, .size = 24},
[C] 0x7fed26401950: {.marked = 0, .size = 24},
[B] 0x7fed264019b0: {.marked = 1, .size = 24},
[A] 0x7fed26401a10: {.marked = 1, .size = 24},
}
标记不会回收垃圾，它只会识别活着的对象。这是一个相对较快的循环——我们只访问活动数据的一小部分。相反，扫描阶段必须遍历整个堆。让我们来看看。
Sweep phase
由于我们跟踪traceInfo数据结构中所有已分配的对象，因此扫描阶段可以利用它进行遍历：
/**
* Sweep phase.
*/
void sweep() {
auto it = traceInfo.cbegin();
while (it != traceInfo.cend()) {
if (it->second->marked) { // (1)
it->second->marked = false;
++it;
} else {
it = traceInfo.erase(it);
delete it->first; // (2)
}
}
}
所以在（1）中，我们检查一个对象是否活着，也就是说，它的标记位被设置了。在这种情况下，我们重置标记位（用于未来的收集周期），并继续进行，将对象保留在堆上。
否则，在跟踪期间没有访问该对象，这意味着它是垃圾，因此在（2）中我们立即回收它。
在扫描阶段之后，我们的堆如下所示：
这也反映在我们的堆转储中——整个右子树都不见了：
------------------------------------------------
After sweep:
{
[B] 0x7fed264019b0: {.marked = 0, .size = 24},
[A] 0x7fed26401a10: {.marked = 0, .size = 24},
}
这基本上就是整个算法！
现在当我们知道它是如何工作的时候，让我们最终深入了解获取指针和根的特定 C++ 细节。
Obtaining pointers
在上面的标记阶段，我们使用了getPointers辅助函数，它返回一个对象的子指针。
我们来看看实现：
/**
* Go through object fields, and see if we have any
* which are recorded in the `traceInfo`.
*/
std::vector<Traceable *> getPointers(Traceable *object) {
auto p = (uint8_t *)object;
auto end = (p + object->getHeader()->size);
std::vector<Traceable *> result;
while (p < end) {
auto address = (Traceable *)*(uintptr_t *)p;
if (traceInfo.count(address) != 0) {
result.emplace_back(address);
}
p++;
}
return result;
}
这里的想法是我们遍历每个字段，看看是否有任何“看起来像一个指针”，以及它是否记录在我们已知的堆地址中。如果是，我们保守地将其视为指针。这也是我们size从对象头进入我们的领域的时候。我将把对误报指针的检查作为一项任务留给你。
好的，现在当我们可以获得子指针时，让我们看看我们如何获得根。
Determining roots
警告：这部分是 C++ 特定的并且是低级的。一般情况下，以下实现细节可以跳过，不是理解 Mark-Sweep 算法本身所必需的。
根，因为我们知道，是一个可到达的活动的引用，其通常由a表示，表示为一个变量或一个寄存器。为此，我们需要扫描当前堆栈（通常是来自活动线程的所有堆栈），并查看某些变量是否存储在寄存器中。
为此，我们介绍读取帧和堆栈指针的过程：
/**
* Frame pointer.
*/
intptr_t *__rbp;
/**
* Stack pointer.
*/
intptr_t *__rsp;
#define __READ_RBP() __asm__ volatile("movq %%rbp, %0" : "=r"(__rbp))
#define __READ_RSP() __asm__ volatile("movq %%rsp, %0" : "=r"(__rsp))
此外，我们gcInit调用的 frommain初始化了主帧地址——这将是我们在堆栈遍历中的停止边界：
/**
* Main frame stack begin.
*/
intptr_t *__stackBegin;
/**
* Initializes address of the main frame.
*/
void gcInit() {
// `main` frame pointer:
__READ_RBP();
__stackBegin = (intptr_t *)*__rbp;
}
注意：也可以使用非标准__builtin_frame_address函数来获取主框架地址。
最后是我们的getRoots函数：
/**
* Traverses the stacks to obtain the roots.
*/
std::vector<Traceable *> getRoots() {
std::vector<Traceable *> result;
// Some local variables (roots) can be stored in registers.
// Use `setjmp` to push them all onto the stack.
jmp_buf jb;
setjmp(jb);
__READ_RSP();
auto rsp = (uint8_t *)__rsp;
auto top = (uint8_t *)__stackBegin;
while (rsp < top) {
auto address = (Traceable *)*(uintptr_t *)rsp;
if (traceInfo.count(address) != 0) {
result.emplace_back(address);
}
rsp++;
}
return result;
}
在这里，我们遍历堆栈，读取当前的%rsp，直到我们到达top设置为 的点为止__stackBegin。
注意：您可能还需要使用__attribute__((noinline))特定函数来保留堆栈帧。
注意我们使用的技巧setjmp。为了使它更简单，并避免手动弄乱寄存器，我们只是将它们全部推送到当前帧上。如果任何可追踪对象在寄存器中，我们的getRoots分析将能够找到它，只遍历堆栈。
在这一点上，我们可以认为我们的实现已经完成。
Conclusion
我希望已经讲明白了了Mark-Sweep垃圾收集器的一些细节，并展示了用低级语言实现它的细节，它暴露了指针语义。在具有可预测值类型的虚拟机中实现标记扫描，并隐藏堆栈帧、寄存器和指针的所有细节，此时应该简单得多。
我们在此处展示的基本实现还有许多其他改进，例如，按代收集，或使用并发标记扫描 (CMS)实现。
此外，Mark-Sweep 是一个非移动收集器，存在堆碎片问题，因为分配器应该重用回收的对象，使它们保持原位。Mark-Compact和Copying收集器解决了这个问题。