动态内存是如何被垃圾收集器遍历的？

Question

我已经阅读了有关不同类型的GC以及它们的工作原理的相关内容。所有类型的GC都涉及遍历可能被回收的内存集合，但是我所读到的内容并没有给出实际操作的指示。下面这样的操作是否完全偏离了正确方向？

void* myAlloc(size_t size)
{
    if (needToGc())
        gc();
    void* obj = malloc(size);
    if (!obj)
        outOfMemory(); // or maybe GC and try once more
    *alloced = obj;
    *alloced = *alloced + 1;
    return obj;
}
void gc()
{
    // go through memory pointed to in `alloced`
}

我猜是这样，但这是我能想到的唯一解释...

- Pete

Answer 1

垃圾收集器有很多种，取决于要求（内存开销、延迟、数据布局等）。我的一些答案可能不适用于一些复杂的收集器。

首先，needToGc是没有必要的：如果malloc失败，则会触发垃圾收集器。

至于内存如何遍历，垃圾收集器的任务是将正在使用的内存与未使用的内存分离，并回收后者。基本原则是，如果内存可以从程序访问到，则它正在使用中。这是通过以下方式确定的：

• 某些根对象被认为是可达的。例如，堆栈上的任何内容都是可达的，任何全局变量都是可达的。

• 如果可达对象指向另一个对象，则该对象也是可达的。

• 剩下的所有内容都是不可达的，因此被认为是未使用的并且可以回收。

当触发垃圾收集器时，它会遍历所有根对象，并对每个根对象递归遍历可达的对象。一旦收集器遍历了所有可达对象，它就会回收未被遍历的对象。

一种简单的遍历技术称为标记-清除。每个对象都包含一个标记位，最初为0。当遍历函数到达一个对象时，它查看标记位：如果标记位为1，则该对象已经被遍历；如果标记位为0，则遍历函数将其设置为1，并在当前对象指向的每个对象上递归调用自身。标记阶段包括为每个根对象调用遍历函数。随后是扫描阶段，它迭代所有分配的对象：如果对象仍然标记为0，则释放它；否则将其标记重置为0。

大多数垃圾收集器都基于标记-清除，尽管通常具有相当多的复杂性。

有关更多信息和其他指针，请参见wikipedia article。

- Gilles 'SO- stop being evil'

---

这描述了所有追踪垃圾收集器的基本操作。然而，还有另一类工作方式完全不同的垃圾收集器：它们被称为引用计数垃圾收集器，它们的工作方式基本上已经在它们的名称中描述了（实际上与追踪收集器一样）。它们计算对象的传入引用数量，当该计数达到0时，所涉及的对象就有资格进行垃圾收集。 - Jörg W Mittag

@Jörg：这已经越来越接近于一场宗教战争了，但许多人（包括我在内）不认为引用计数是垃圾收集器（它可能是其中的一部分）。引用计数不能收集循环垃圾（即A指向B指向C指向...指向A，它们中没有一个可以从根节点到达）。例如，这使得引用计数对于函数式编程毫无用处（它不会收集递归函数的闭包）。 - Gilles 'SO- stop being evil'

@Peter：gc 不需要知道 malloc 把内存放在哪里。对于建立在 malloc 之上的 gc，myAlloc 可能需要跟踪分配的块，因为当它们变得不可达时，gc 需要将它们传递给 free。但是它可以使用比数组更好的数据结构。如果 gc 知道 malloc 的实现方式，它可以直接修改堆以标记不可达块为可用状态，然后 myAlloc 就不需要跟踪任何东西了。gc 知道从根节点遍历什么。 - Gilles 'SO- stop being evil'

@Peter：你在写垃圾回收器吗？如果是的话，首先要确保它正确无误，这并不容易！此外，阅读一些Hans Boehm的论文，他为C和C++编写了事实上的标准保守式垃圾回收器。 - Gilles 'SO- stop being evil'

@Peter：对于在malloc之上的垃圾回收，myAlloc中的结构需要是指向分配块的集合指针。哈希表或基于trie的数据结构将是速度、内存开销和简单性之间的合理折衷。您可以使用类似的表来跟踪收集期间标记的块。 - Gilles 'SO- stop being evil'