物联网平台设计文档：精简GC（垃圾回收）

许多高级编程语言的自动内存管理功能让编程变成了比较容易的一件事。然而，嵌入式平台经常缺少这一部分功能，这是有原因的：现代垃圾收集（GC）系统使用的成熟技术设计，与嵌入式系统只有几KB内存可用的的折衷方案相比完全不同。

用于嵌入式平台的优秀GC是实现JavaScript等高级语言的关键，也是让程序员更喜欢嵌入式编程的关键。

这篇文章展示了V7垃圾收集器其中一个部分的背后设计细节。首先了解一下背景知识。

总所周知，实现高级语言垃圾收集的一个关键是减少内存碎片。管理可变长度对象（如字符串）时，这尤其成为问题关键。

解决完全托管堆上下文的碎片问题的最有效方法之一是精简垃圾收集器。想法是这样的，我们不仅仅自动回收未使用的内存范围，而且将已使用的内存组合在一起而没有任何缝隙。但是，因为我们正在移动程序主动使用的内存块，所以我们需要能够更新对其新位置的所有引用。

事实证明，更新所有引用要求我们将一些块引用信息存储在内存中，并且在嵌入式平台上，每个字节都需要考虑到。

这实在是老生常谈。我们选择的收集器算法是Morris78。有趣的是我在重新创作之后才发现了之前的作品。直到我知道去找什么，我才发现了这篇比你们现在看到的整整早一年文章。

一如既往，我们的设计文档不是产品文档，而是对我们决策的看法。您可以查看Mongoose IoT Platform了解文档是如何实现的。

精简GC

目的

为可变大小的对象（如字符串），选择和描述较低的空间开销和较低的时间复杂度的垃圾收集器。

背景

我们需要一种节省空间的内存布局和垃圾收集技术来处理字符串和其他可变长度的东西。

概述

Mark-compact收集器，最初在Morris78中描述。

我们首先设想一个包含可变长度块的堆。每个块在开头包含一个长度字段（长度字段可以用可变长度编码实现）。

区块通过指针分配，分配总是从缓冲区的头部开始，并在缓冲区的头部记录新分配的区块的长度。

因此，所有分配的块都位于缓冲区的头部，而缓冲区的余下部分包含未分配的空间。mbuf结构可以用来表示这样一个缓冲区。

减少代码复杂度和空间使用的关键是通过压缩来释放块，而不是维护空闲列表（受外部碎片影响）。

我们选择将长度字段作为块的一部分，因为我们仍然需要它用于字符串表示（参见更多）。这种方案的一个变体可以像其他分配器那样在分配区域之前保持长度字段。

这种类型的堆的最小块大小等于指针的大小。假设我们可以存储六个字符组成的字符串，那么在这种堆中，最短的字符串有8个字节（一个字节存储长度，另七个存储数据），以便最长的指针的能够被存储。相比之下，基于表格的压缩的最小块大小至少为两个指针大小。

为了简单起见，我们来看看当堆只包含原始数据，并且所有传入指针都被保存在其他地方（例如在固定宽度的单位中）时是什么情况：

多个值可以指向一个块，并且每个块的有效载荷都一样，即指向块的指针。当我们需要移动块时，所有这些值都必须更新。有一种简单的方法可以跟踪所有要更新的值，事实上，块的第一个sizeof(void *)个字节必须保留。我们可以把第一个字节叫做块头。（在可变长度len编码的情况下，块头包含字符串大小和字符串有效载荷的一些初始字节）

遍历由对象组成的图时，每当指针值被标记为指向这种堆的指针（例如字符串指针）时，我们将块头的值放入val_t有效载荷中，并将指向val_t位置的指针存到块头：

在第二次图遍历期间遇到指向该块的指针时，我们会重复刚刚的步骤。

到遍历结束时，所有有效块的块头都指向存储val_t地址的链表，当块被移动时，将使用块的新地址更新val_t位置。

我们还需要以某种方式区分有效块和无效块。我们可以使用占一个比特的标签来区分块头中的长度字段和val_t指针。有关如何使用varint长度编码来实现的详细信息，请参见下面的详细设计部分。

压缩阶段从第一个块开始。由于直到分配区域末尾的所有块在垃圾收集之前都是有效的，所以每个块都包含有效的长度字段，可用于跳到下一个块。mbuf len设置为0，并记录旧的mbuf len。

遇到一个标记的块（在块头中有一个val_t指针的块）时，它会被移动到mbuf的末尾（现在从0开始），并且链表被遍历，直到碰到len的sentinel值，并且这个值被目的地的地址更新。最后，sizeof(void *)字节在块头中恢复，继续扫描下一个块，直到到达旧的mbuf长度。

详细设计

Varint len

如果我们限制块的长度永远不为0（这对于字符串来说是可以的，因为小的字符串使用值内联），我们可以使用第一个0字节来标记修正地址。

我们只需要将指针存储在前导0字节之后。

64位指针按照我们在v7_value_to_pointer中的做法，被存储为48位值并进行符号扩展：

struct {
    uint64_t s:48;
} h ;

编码：

h.s = p;
memcpy(chunk +1,&h.s,6);

解码：

memcpy(&h.s, chunk +1,6);
p = h.s

块内部的指针

如果这种类型的堆被用来存储包含指针的块... 尚未解决。

注意事项

• 块大小是明确的，并且是“用户”可访问有效负载的一部分。
• 分配器需要知道最小的块的大小，并且这个值要对“用户”可见。

这两个注意事项都很好，因为用户是虚拟机，并且我们希望能够使用块的内容作为`v7_str`值。

长度分析

原来只有65行代码！它们没有被写的很晦涩，只是......密集；V7中最密集且最难读的部分。

参考

http://cs.ucsb.edu/~ckrintz/racelab/gc/papers/morris-compaction.pdf