垃圾收集
Cello 提供了一个基本的垃圾收集器，可用于避免手动释放内存。
垃圾收集对象是通过new函数分配的，并且可以（可选地）通过删除del。Cello 中的垃圾收集器也可以在编译时使用该标志禁用，-DCELLO_NGC而不会影响标准库，标准库使用del任何一种方式来管理其内存。禁用时，必须使用new和手动管理内存del。要在避免垃圾收集器（不完全禁用它）的同时分配内存，可以使用new_raw和函数。del_raw
使用 Cello Garbage Collector 时需要注意以下几点：
- 可达性
Garbage Collectable 对象必须可以通过堆栈上的局部变量或通过其他 GC 分配的自身可访问的 Cello 对象链访问。它们不能存储在全局/静态变量中，或者只能通过非 Cello 结构访问的位置。此外，Cello 中的每个线程都有自己的垃圾收集器，它在本地运行，因此对象不应分配在一个线程中，而只能从另一个线程访问。要将 Cello 对象存储在全局/静态位置或非 Cello 结构中，new_root应使用该函数，并使用del_root. 由于这些限制，最好将 Cello 垃圾收集器视为一种 调用对象析构函数的惰性RAII对象超出范围后的一段时间。
- 马克班
默认情况下，Cello 垃圾收集器仅扫描对象的内存以查找指向它已分配的其他 Cello 对象的指针，但可以通过实现Mark类来覆盖此行为。如果您创建一个 Cello 类型，它自己进行内存分配并将 Cello 对象存储在该内存中，您可以定义此类以允许它与 GC 正确交互。
- 实时采集
大提琴中的垃圾收集仍然有些新的和实验性的。它使用一种简单的停止世界标记和扫描算法。这可能会导致相当长的暂停，因此不适用于实时应用程序。
- 未初始化的值
垃圾收集器扫描堆栈内存，这自然包含未初始化的值。尽管这样做是安全的，但如果您通过 Valgrind 运行 Cello 程序，这些访问将被报告为错误。除了这个 Cello，在 Valgrind 中不应该有任何内存错误，因此禁用这些以检查任何实际问题的最简单方法是使用选项运行 Valgrind --undef-value-errors=no。
- 可移植性
根本没有办法在 C 中创建一个完全可移植的垃圾收集器。但与Boehm 垃圾收集器不同，Cello 垃圾收集器不需要使用任何特定于平台的技巧。它所依赖的只是架构使用调用堆栈来实现功能框架的假设。这意味着它应该可以安全地用于或多或少在野外发现的所有架构。
这个怎么运作
那么如何在 C 中进行垃圾收集呢？
对于基本的标记和清除垃圾收集器，您需要两件事。您需要的第一件事是所有已分配对象的列表。第二个是仍在范围内的所有对象的列表 -程序/程序员可以访问的所有对象。
然后标记和清除垃圾收集器只是比较这两个列表。如果一个对象已被分配，但程序/程序员无法访问，则可以将其删除。它真的是那么简单。
分配对象的列表通常很容易获得。您只需这样做，以便您的内存分配函数记录它所做的所有分配。只要所有分配都通过此功能进行，您就可以了。在 Cello 中，所有可垃圾回收对象的分配都必须经过new，因此每当分配新对象时记录都不会出现问题。
可到达对象的列表通常更难获得。在诸如 Java 之类的在虚拟机上运行的语言中，这可以通过遍历表示在虚拟机上运行的程序的数据结构、查找对对象的所有引用并跟踪这些对象包含的任何更多引用来实现。
在这种情况下，可达对象的列表没有明确计算。相反，比较是通过标记然后扫描来隐式完成的。首先标记所有可达对象，从局部变量和全局变量开始，递归地跟随程序中的引用，标记所有对象，直到不再找到任何未标记的对象。然后通过遍历并删除任何未标记的对象来扫描已分配对象的列表。
但是 C 的工作抽象级别比这些语言低。没有方便的“对象”或“参考”列表可供参考。在 C 中，我们正在处理原始内存，并且所有这些结构都不存在。幸运的是，由于 Cello 作为原生 C 之上的运行时系统，我们可以将它与一些巧妙的技巧一起使用来尝试重建这种结构的大部分 - 这样做可以创建一个仅限于 Cello 对象的基本垃圾收集器。
我们可以从观察开始，一般来说，C 中的内存存在于三个位置——堆、堆栈和数据段。这意味着如果程序可以访问一个对象，则在这些区域之一中必须存在指向它的指针。
给定一个由我们的 GC 进行的所有分配的列表，我们应该能够搜索这些内存位置（不包括分配列表本身），如果我们找到指向 GC 分配的任何内存的指针，我们知道它仍然可以被程序等不应被删除。如果我们没有找到指向分配的指针，则程序必须不再使用它，因此可以将其删除。现在的问题是如何搜索这些内存位置。他们在哪里？他们的界限是什么？
不幸的是，对于数据段，没有可移植的方法来查找，因此对于 Cello 垃圾收集器，我们只是忽略它并告诉用户不要使用垃圾收集器分配全局变量！
对于堆也是如此——要求我们的用户仅从其他 Cello 对象引用可垃圾回收的 Cello 对象是合理的。这意味着我们将搜索限制在通过 Cello 创建的堆对象上。我们的 Cello 运行时知道分配的每个堆对象的分配大小，因此我们可以扫描每个对象的内存以查找指向其他 Cello 对象的指针。如果对象做了一些自定义的内存分配，我们可以让它实现Mark类型类来直接告诉我们它指向什么对象。
由于忽略了数据段，并且堆很容易扫描，这就留下了最终的，可以说是最重要的指向 Cello 对象的指针的位置，即堆栈。现在，在几乎所有 C 的合理实现中，堆栈是一个连续的内存区域，对于每个函数调用都会向下增长（或有时向上，尽管这并没有太大区别）。它包含函数使用的所有局部变量以及各种其他内务数据。通过获取栈顶和栈底的内存地址，我们可以扫描中间的所有内存并检查它是否有指向 Cello 对象的指针。
假设堆栈从顶部到底部增长，我们可以通过获取一些局部变量的地址来获得堆栈底部的保守近似值：
void* Cello_GC_Stack_Bot() {
void* p = NULL;
return &p;
}
但在我们这样做之前，我们需要确保两件事。首先，我们要确保将寄存器中的所有值都刷新到堆栈中，这样我们就不会错过隐藏在寄存器中的指针，其次，我们要确保Cello_GC_Stack_Bot函数没有被编译器内联。我们可以通过某种可移植的方式将寄存器溢出到堆栈内存中setjmp- 将寄存器放入jmp_buf变量中。并且我们可以通过仅通过函数指针调用标记函数来确保函数不被内联，函数指针的值由易失变量决定（易失变量不受优化影响）。然后我们知道该Cello_GC_Stack_Bot 函数将返回一个地址，该地址肯定会覆盖溢出的寄存器以及我们调用上方堆栈中的所有其他内容。
void Cello_GC_Mark_Prelude() {
jmp_buf env;
setjmp(env);
volatile int noinline = 1;
void (*mark_stack)(void) = noinline
? Cello_GC_Mark_Stack
: (var(*)(void))(NULL);
mark_stack();
}
获取栈顶有点困难，但假设用户程序从头开始，main我们可以使用一个非常厚颜无耻的宏将其包装在一个自定义函数中，该函数首先向 Cello GC 注册一些局部变量的地址，然后调用用户程序：
int Cello_Main(int argc, char** argv);
#define main(...) \
main(int argc, char** argv) { \
var stk = NULL; \
Cello_GC_Init(&stk); \
return Cello_Main(argc, argv); \
}; \
int Cello_Main(int argc, char** argv)
使用这些技术，我们可以获得堆栈内存区域的安全近似上限和下限，该区域应该包含指向垃圾回收对象的所有相关指针。现在我们需要做的就是扫描这个内存范围并标记我们发现引用的任何指针。
void Cello_Mark(void) {
var top = Cello_GC_Stack_Top();
var bot = Cello_GC_Stack_Bot();
for (var p = top; p <= bot; p += sizeof(var)) {
Cello_GC_Mark_Item(*((var*)p));
}
}
但是我们如何判断某个内存块是否真的是一个指针呢？我们不想鲁莽地跟随指针，否则我们可能会导致段错误。现在一般来说，没有办法区分一些看起来像指针的内存和实际的指针本身——但是我们可以使用一些启发式方法来忽略许多潜在的地址。
首先 - 指针必须是内存对齐的 - 这意味着对于 64 位机器，它们只能位于每个 8 字节边界，并且只能指向 8 字节边界上的某个值。这意味着指针值必须是指针大小的倍数，并且指针的地址必须是指针大小的倍数。我们还可以跟踪我们分配的最大和最小指针地址，并快速忽略这些边界之外的任何内容。
这些简单的措施将阻止我们在几乎所有情况下跟踪错误或无效的指针，但我们需要进一步缩小范围，因为错误的内存访问可能会使程序崩溃。为此目的，维护了一个哈希表，其中存储了 Cello 分配的所有指针。它可用于快速检查指针是否指向已分配的 Cello 对象。
这是函数的Cello_GC_Mark_Item大致样子。它进行这些简短的检查，然后在成功时进行实际的标记和递归。
void Cello_GC_Mark_Item(var a) {
if (a % sizeof(var) is 0
and a >= minptr
and a <= maxptr
and Cello_GC_Allocated(a)
and not Cello_GC_Marked(a)) {
Cello_GC_Mark(a);
Cello_GC_Recurse(a);
}
}
递归函数也很简单。它要么调用markCello 对象上的函数，要么扫描该位置的内存并尝试将每个内存段标记为指针 - 就像堆栈数据一样。
static void Cello_GC_Recurse(struct GC* gc, var ptr) {
var type = type_of(ptr);
struct Mark* m = type_instance(type, Mark);
if (m and m->mark) {
m->mark(ptr, gc, (void(*)(var,void*))GC_Mark_Item);
return;
}
struct Size* s = type_instance(type, Size);
if (s and s->size) {
for (size_t i = 0; i < s->size(); i += sizeof(var)) {
var p = ((char*)ptr) + i;
GC_Mark_Item(gc, *((var*)p));
}
return;
}
}
这完成了标记阶段所需的所有工作。清扫阶段同样简单。它只是删除了所有未标记的大提琴对象！再次大致看起来像这样：
void Cello_Sweep(void) {
for (size_t i = 0; i < Cello_GC_NumItems(); i++) {
var ptr = Cello_GC_Item(i);
if (Cello_GC_Marked(ptr)) {
Cello_GC_Unmark(ptr);
} else {
Cello_GC_Delete(ptr);
}
}
}
现在，当用户请求一个新的分配时new，内存使用量超过了某个界限，我们只需调用Cello_Mark并Cello_Sweep释放任何可用内存。
正如您可能怀疑的那样，实际上还有更多工作要做，对此处的代码片段中显示的内容进行了各种优化和调整，但是 Cello Garbage Collector 仍然非常简单、安全和便携 - 如果有点慢！
总的来说，我希望我已经证明了用于有限环境的简单垃圾收集不仅在 C 中是可能的——它的实现和理解都相当简单。
网友评论