云风的 BLOG

lua 可以自定义内存管理器。只是一个 lua_Alloc 函数而已。一般，我们会使用标准的 malloc/free/realloc 来模拟。有时，我们信不过 libc/msvcrt 的管理器，会选择一个看起来更好的。

但是，lua_Alloc 的行为和 realloc 等还不完全一样。它提供更多信息。比如它可以准确的指出每个内存块的大小。而标准 api 则做不到这点。通用内存管理器需要使用一个 cookie 来记录数据块的长度，如果你自己实现内存管理器的话，则可以省掉这个 cookie 。

如果你前面有读完 GC 的代码，你会发现，其实 Lua 使用内存是很有规律的。它会在 GC 的 sweep 之前只增不减。然后大批量的释放内存。如果我们想把 GC 放在独立线程中，表面上看需要保证内存管理器的线程安全。但实际上不必要做的那么严格。

释放内存一定只存在 sweep 流程中（除非用户主动调用了 lua_Alloc ，这就意味着，我们可以做一些优化。并不一定要保证严格的线程安全。

内存申请可以是在一整块内存上简单的循序切分，即，每要一块内存，就简单的从整块中切下来（只是调整一下指针），当 sweep 发生时，把备用内存块切换到新的整块上去，让 sweep 流程可以安全在老的内存上工作。因为没有 cookie ，不用链表，sweep 对内存管理器的操作和逻辑主线程是完全独立的，不需要任何锁。

sweep 过程可以是缓慢的（因为已经独立开去），它可以先将所有释放的内存用链表串起来，然后用一个简单的链表冒泡排序，之后就可以把释放的内存块做合并了。少量的用户主动调用的内存释放（一般也是在 userdata 的 gc 元方法里），可以放到请求一个队列中，留到 GC 线程统一处理。除了用户主动调用的内存释放操作，还有一个 realloc 请求，需要释放旧有的空间，申请新的空间。这些更常见，也需要记录。

sweep 完成后，通常可以回收到整块的连续内存，就可以把最大的一块拿来下次使用了。

内存管理器的优化倒不一定必须在独立线程 GC 中用。完全可以单独写一个提供给现在不加修改的 lua 。如果想优化上面的算法，那步对 freelist 的冒泡排序以及整理，倒是可以私下开一个线程。

我们不必把整个 GC 模块都搬到独立线程中去，只考虑那些耗时的工作即可。这样可以最大限量的避免修改 lua 已有的代码。比如只需要考虑 singlestep 里的大运算量部分。

先看 sweep 流程的并行化。关键在于 GCSpropagate 流程中的 propagatemark 函数。atomic 函数完全可以放在主逻辑线程中运行。

propagatemark 的原则是一次只处理一个 GCObject 对象。简单的修改方法是给正在处理的对象加锁。自然不需要为每个 GCObject 都加一个锁，那样太浪费内存。既然一次只有一个，那么在锁里记录正在处理的对象即可。对 TTABLE , TFUNCTION , TTHREAD , TPROTO 的修改都判定这个锁。主逻辑里，被锁 block 住的可能性是非常低的，那只在 GC 刚好运行到同一个对象时才会碰到。

但是对锁的判断可能依然是一个比较大的开销。我们可以先判定 GC 的状态是否处于 GCSpropagate ，这个判断是不需要锁的（因为 gc 的流程状态切换在主线程中）。只要在 GCSpropagate 流程才需要做锁的处理。

TTHREAD 也是一个开销比较大的地方，lua gc 的原始代码中，特地把 thread 放到了 gcagain 里，推迟到 atomic 阶段再扫描一次，而不是对 stack 的修改都做一个特别的 write barrier 也有这方面的顾虑。毕竟大多数的 lua 运算都是基于 local 的。这相当于所有的 local 变量访问都要做 barrier 。

我的解决方案是，当 GC 扫描到 TTHREAD 时，暂时 stop the world ，而不是做锁。这个 stop 当然要经过协调。原本调用 luaC_checkGC 的地方都是一个好的切入点。因为 luaC_checkGC 有可能调用 singlestep ，也就是说，lua 原本的设计就保证了在这些位置插入 GCSpropagate 是安全的。这样，我们的 GC 线程扫描到 TTHREAD 类型时，可以发出信号等待主线程暂停。然后就可以安心的做上一个步骤，再放行主线程继续。

另一个需要特别处理的 write barrier 。write barrier 会比以前稍昂贵，这里也需要仔细考量一下。

write barrier 做的工作其实是当 A 关联到 B 时，检查是否需要把 A mark 一下（当 B 不是 table），或把 B 放入 gray 链（当 B 是一个 table）。如果改成多线程版本的话，直接判断 marked 位状态变得不太合适。我建议这样实现：先判定 GC 是否处于 GCSpropagate 以决定是否需要 barrier 。如果需要，则把需要关联的 A 和 B 放进一个 FIFO 的管道。然后在 GC 线程中，每做一个 singlestep 就检查这个管道，逐个处理 barrier 。极端情况下，这个管道上的 barrier 请求速度快过处理速度（需要实测看是否真的可能发生），则采用上面 TTHREAD 的处理方式暂停主逻辑线程。

GCSsweepstring 流程，在 lstring.c 里加一把锁是很容易并行化的。这个锁只在创建新 string 时才会遇到，所以不会读主逻辑有太大的影响。

GCSsweep 流程几乎是可以直接并行处理的。因为 GCObject 是条单向链表（分为两段，userdata 是后半段），增加新节点都是在链表头加，而 sweep 则都是修改链表中间，相互不影响。需要特殊对待的是 open upvalue ，这个在之前分析代码时已经讨论过。匹配新的 upvalue 时应该加锁处理。这个过程实际运行时触发不会很频繁，写的时候需要小心而已。

GCSfinalize 不太推荐在独立线程处理，毕竟它会调用一段 lua 代码，同一个 lua state 中的代码是不合适并行化的。

以上即总体思路，期望可以顺利完成这项工作。