为什么我要实现一个安全的Rust并发循环收集器

为什么我要实现一个安全的Rust并发循环收集器

Rust是一种伟大的语言。它在对象和分配的内存布局方面给了你很大的控制权，但是通过它的借用检查系统，你对这些对象寿命的使用被正确管理：如果你拿了一个对象的指针，你必须向编译器静态地证明这个指针寿命永远不会超过这个对象。

在大多数情况下，这不会有什么问题：你创建了一些对象，得到了它们的指针，并做了一些操作，完成了这些操作，所有的指针都消失了，然后销毁所有的对象。然而，更复杂的程序就有问题了，特别是当 "谁负责销毁这个对象？"这个问题并不能很好回答，需要多做一些工作。

C++有一个shared_ptr<T>类型，用于一个对象的引用计数的指针。每当你复制shared_ptr时，它就会增加一个计数器；每当你销毁shared_ptr时，你就会减少这个计数器。一旦计数器归零，你就可以销毁shared_ptr指向的对象，因为你知道你是最后一个可以访问该对象的人，并且可以在你离开时锁上门。

Rust在其Rc<T>和Arc<T>类型中也有同样的内容（Rc是 "引用计数"，Arc是 "原子引用计数"--Arc可以在线程之间安全共享，计数的增减使用原子操作）。
不同的是：
C++并没有用shared_ptr来修复所有的内存安全错误。解除对shared_ptr的引用会给你一个原始指针，你可以错误地持有这个指针而不去破坏它所来自的shared_ptr，否则可能会破坏这个对象。
Rust的Rc智能指针给了你一个借用其内容的机会，因此这是由编译器保证不会超过它们所借用的对象（即Rc）的寿命。

Rust还通过它的Arc类型来防止数据竞赛；shared_ptr和Arc一样，在不同的线程中增加和减少指向同一个对象的计数对它们都是安全的，但是shared_ptr却容易发生数据竞赛，例如，如果两个线程同时试图写入对象，或者一个正在写入，而另一个正在读取同一个内存位置。Rust只给你一个指向Rc或Arc指针内容的只读指针，所以为了改变Arc后面的对象，你需要使用Rust的一个 "内部突变 "类型，比如RefCell<T>，它做一个动态检查，要么有几个指向该对象的只读指针，要么有一个读写指针，但不能同时存在，否则它会恐慌panic并使程序崩溃。
通常Rust使用它的借用检查器系统来执行“读xor写”的访问不变性，但是因为你对对象有非一般的所有权，你不能使用借用检查器，必须在运行时而不是编译时进行这些检查。

这一切都很好：有了shared_ptrs或Arc，你就可以制作大的纠结的数据结构，都指向彼此。
你可以做一个双链接的列表，或者一个带有指向节点的边缘的图，或者一个带有 "父 "链接的红黑树。

问题是它会泄漏内存，最终你的程序会变得非常慢，然后死亡。
出了什么问题？

死循环
shared_ptr和Arc有同样的问题：它们有一个计数器，它们将其维护为指向该对象的现有指针的数量。
如果你有一个像A<->B这样的对象循环，其中A和B是两个不同的对象，但都有指向对方的指针，那么这两个对象的计数都是1，因而不能被删除，因为它们仍然可以从某个地方访问。
如果你的程序已经销毁了对A或B的所有其他引用，那么除了通过A与B彼此的内部指针外，它们是无法被访问的，它们可以安全地被销毁，它们是垃圾，因为你的程序没有任何可能（正确）的方式来访问这些内存，理论上是这样。
但实际不是，因为引用计数没有聪明到知道可访问和不可访问的指针之间的区别，而只是看到这两个对象在某处有一个引用计数的指针，还不能被销毁。

这是个相当糟糕的问题：
在Rust或C++中，通常的解决方案是使用一个竞技场分配器arena allocator，即先分配一个内存区域，然后在该区域内可以有指向其他竞技场对象的对象，最后再释放整个竞技场。
这并不是一个很好的解决方案，因为你本质上还是在泄露内存，只是最终你会在拆毁整个竞技场时释放这些泄露的内存，而不是在任何时候。

你也可以使用一个真正的垃圾收集器，比如shredder或者boehm-demers-weiser GC。这些会偶尔对所有可触及的对象进行扫描，释放其他的东西--它们并不关心周期，因为如果对象的周期从任何线程都无法触及，它们就不会被标记为可触及，从而被释放，因为它们并不保持精确的引用计数。

你真的可以把竞技场分配器看作是半空间垃圾收集器的坏版本，在那里你只能做一次收集，而且总是释放所有的东西：这显然还是有用的，因为它保证你所有的内存被回收，但有明显的缺点。

我对shredder，或rust-gc，或其他几个Rust垃圾收集器库的问题是，它们很复杂。它们中的很多都有新的方案来确保你的程序在任何时候都能正确地维护一组初始可达对象（"根"），因为如果它不这样做，你就会不正确地释放内存并崩溃（或更糟），而且它们对正确管理这些根没有很高的信心，因此有关于没有为生产做好准备的警告。所有(?)的程序也都有stop-the-world阶段，它们必须暂停你进程中每一个正在运行的线程，以便从一个连贯的视图中扫描所有的根（或者根本就不支持多线程！）。

垃圾收集
事实证明，垃圾收集有一个巧妙的变体，叫做循环收集。几个月前，我正在思考所有的Rust垃圾收集器是多么的复杂，以及为什么没有一个Arc-but-doesnt-leak的替代智能指针，你可以把它放到需要它的程序中，我那昏昏沉沉的大脑挖出了我在几年前读《参考计数系统中的并发循环收集》时的一半记忆。然后我在推特上轻率而自信地讲述了如何在Rust中制作一个非常简单的Arc-but-doesnt-leak替代智能指针库，并根据我记得的一般原则进行了设计。

然后，我真的重新阅读了这篇论文，发现它的对象颜色状态转换图是这样的：

循环收集方案的基本思想是，默认情况下，对象与引用计数相同。不同的是，当你的计数被递减到0以外的数字时，你会将对象添加到一个列表中，然后在进行垃圾收集时，你会扫描列表中的所有对象（递归地访问每个对象所能到达的所有对象），看其中是否有对象形成图，其中所有对象的引用都只用内部指针来说明。我们的想法是，为了形成一个循环，你必须要有一个突变器线程。

• 创建一个对象A
• 创建一个对象B
• 增加A的refcount并创建A2，并设置B.ptr = A2
• 设置A.ptr = B（原来的B）
• 销毁A，它是进入对象循环的最后一个外部指针。

...
详细点击标题

Samsara是我的库，它提供了一种Gc<T>类型，该类型是使用循环集合智能指针计数的引用。
它是一个并发的垃圾收集器，潜在的不可及的列表扫描发生在另一个线程上（只通过手动触发，目前没有通过启发式iscs自动进行）。而且，与我所知的其他Rust垃圾收集器不同，它没有一个全局性的 "停止世界 "阶段：如果收集器在扫描Gc对象时，突变器线程试图从该对象获取读写引用，它偶尔会阻塞突变器线程，但这应该是非常短暂的（因为它只是在访问该对象时持有读锁，而不是整个子图）。它也不会像其他一些垃圾收集器那样，通过信号或任何东西中断线程的安全点。