专栏首页用户1191492的专栏物联网平台设计文档:精简GC(垃圾回收)

物联网平台设计文档:精简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 条评论
登录 后参与评论

相关文章

  • JVM 垃圾收集器

    GC算法(引用计数/复制/标清/标整)是内存回收的方法论,垃圾收集器就是算法落地实现。

    万能青年
  • Mono 3 的默认Gc是Sgen

    Mono 3现在是默认 GC是SGen 垃圾回收器,垃圾回收器几个性能和扩展性方面的改进,以更好地利用多核处理器硬件。SGen 已移植到 Windows 和 M...

    张善友
  • JAVA垃圾回收机制

    PS:不管是调优也好,先是配合对应的新老对应的垃圾收集器,如果有必要才修改垃圾收集器的参数的,垃圾回收器如何标记垃圾,如何进行垃圾收集的,收集器有哪些?它们是如...

    IT架构圈
  • Java 12 新特性概述

    Java 12 已如期于 3 月 19 日正式发布,此次更新是 Java 11 这一长期支持版本发布之后的一次常规更新,截至目前,Java 半年为发布周期,并且...

    beifengtz
  • JVM 看这一篇就够了

    本文转自 https://blog.csdn.net/qq_46153765/article/details/113092445,如有侵权,请联系删除。

    麦洛
  • 垃圾收集器详解及参数配置

    client模式下默认的垃圾收集器组合,可通过-XX:+UseSerialGC强制开启。非常适合运行于客户端PC的小型应用程序,或者桌面应用程序(比如swing...

    ydymz
  • 我眼中的G1 GC

    7岁那年,当我合上《上下五千年》一套三册全书时,我对自己说,我想当个作家。这一晃27年了,等待了27年,我的第一本书《大话Java性能优化》在2016年4月正式...

    博文视点Broadview
  • 一文理清JVM和GC 【第二弹】

    程序在垃圾回收上花费了98%的时间,却收集不会2%的空间。 假如不抛出GC overhead limit,会造成:

    蔡不菜丶
  • Go垃圾回收 1:历史和原理

    新老朋友好久不见,我是大彬。今天为大家带来的分享是Go语言垃圾回收,这篇文章筹划的了很久,因为GC也是很强大的一个话题,关于GC已经有很多篇论文还有书籍,想通过...

    大彬
  • Java 9许愿清单:请赐予我们更理想的垃圾回收机制

    我是攻城师
  • JVM垃圾回收器、内存分配与回收策略

    新生代垃圾收集器 1. Serial收集器 serial收集器即串行收集器,是一个单线程收集器。

    大数据学习与分享
  • 大型跨境电商 JVM 调优经历

    前提: 某大型跨境电商业务发展非常快,线上机器扩容也很频繁,但是对于线上机器的运行情况,特别是jvm内存的情况,一直没有一个统一的标准来给到各个应用服务的own...

    芋道源码
  • JVM-5. 垃圾回收器

    悠扬前奏
  • 【进击面试_04】Java 虚拟机

    JVM 是 Java 虚拟机 Java Virtual Machine 的缩写,JVM 是一种用于计算设备的规范,它是一个虚构出来的计算机,是通过在实际的计算机...

    Demo_Null
  • 前京东陌陌高级架构师的直播笔记分享(Java 内存问题排查和解决:内存概览,内存问题出现的原因,问题代码,案例分析)

    上一周我有幸观看了高级架构师李国讲师的直播,内容是关于 Java 内存问题排查和解决。

    RendaZhang
  • Java虚拟机知识点快速复习手册(上)

    https://blog.csdn.net/o_nianchenzi_o/article/details/78629929

    Rude3Knife的公众号
  • 【转】一文看懂JVM内存布局及GC原理

    杨俊明,携程云客服平台研发部软件技术专家。从事IT行业10余年,腾讯云+社区、阿里云栖社区、华为云社区认证专家。近年来主要研究分布式架构、微服务、Java技术等...

    yiduwangkai
  • 干货 | 一文看懂JVM内存布局及GC原理

    杨俊明,携程云客服平台研发部软件技术专家。从事IT行业10余年,腾讯云+社区、阿里云栖社区、华为云社区认证专家。近年来主要研究分布式架构、微服务、java技术等...

    携程技术
  • CLR和.Net对象生存周期

    标签:GC .Net C# CLR 前言 对象的生存周期和垃圾回收一直是容易被我们忽略的知识点,因为我们现在高级语言编程平台太“智能”了,自动的异常处理,内存管...

    潘成涛

扫码关注云+社区

领取腾讯云代金券