物联网平台设计文档:精简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

本文的版权归 用户1191492 所有,如需转载请联系作者。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

技术 | Python从零开始系列连载(二十七)

为了解答大家学习Python时遇到各种常见问题,小灯塔特地整理了一系列从零开始的入门到熟练的系列连载,每周五准时推出,欢迎大家学积极学习转载~

12430
来自专栏阮一峰的网络日志

Javascript编程风格

Douglas Crockford是Javascript权威,Json格式就是他的发明。 去年11月他有一个演讲(Youtube),谈到了好的Javascrip...

36360
来自专栏北京马哥教育

让你的 Python 代码优雅又地道

学Python最简单的方法是什么?推荐阅读:Python开发工程师成长魔法 译序 如果说优雅也有缺点的话,那就是你需要艰巨的工作才能得到它,需要良好的教育才能欣...

409100
来自专栏木可大大

编写优雅代码的最佳实践

Robert Martin曾说过"在代码阅读中说脏话的频率是衡量代码质量额唯一标准"。同时,代码的写法应当使别人理解它所需的时间最小化,也就是说我们写的代码是给...

10320
来自专栏lgp20151222

Java的常量接口思考,项目中的常量是放在接口里还是放在类里呢?

最近在看一本书 Java与模式,里面提了一句不建议使用常量接口,甚至举了个java源码的反例,

14610
来自专栏Spark学习技巧

你真知道如何高效用mapPartitions吗?

做过一段时间spark的应用开发的小伙伴都会渐渐发现,很没趣,因为都是调API。那么,真的是没趣吗,还是说你本身没有去深入研究呢?通过本文你就会发现自己没成长是...

27920
来自专栏老九学堂

1分钟彻底理解C语言指针的概念

计算机中所有的数据都必须放在内存中,不同类型的数据占用的字节数不一样,例如 int 占用4个字节,char 占用1个字节。为了正确地访问这些数据,必须为每个字节...

53580
来自专栏企鹅号快讯

30分钟学会用Python编写简单程序

参与文末每日话题讨论,赠送异步新书 异步图书君 学习目标 知道有序的软件开发过程的步骤。 了解遵循输入、处理、输出(IPO)模式的程序,并能够以简单的方式修改它...

722100
来自专栏小李刀刀的专栏

[译]Laravel 5.0 之 Eloquent 属性转换

本文译自 Matt Stauffer 的系列文章. ---- 之前完全忘了要把这个 Laravel 5 的系列博客写完,不过最近看到了一篇关于属性转换的简介 L...

44380
来自专栏老马说编程

计算机程序的思维逻辑 (9) - 强大的循环

循环 上节我们介绍了流程控制中的条件执行,根据具体条件不同执行不同操作。本节我们介绍流程控制中的循环,所谓循环就是多次重复执行某些类似的操作,这个操作一般不是...

22180

扫码关注云+社区

领取腾讯云代金券