Sound garbage collection for C using pointer provenance
Sound garbage collection for C using pointer provenance
复制标题
使用指针来源的 C 健全垃圾收集
DOI：
10.1145/3428244
复制
发表时间：
2020
影响因子：
--
通讯作者：
Narayanasamy, Satish
中科院分区：
文献类型：
--
作者：
Banerjee, Subarno;Devecsery, David;Chen, Peter M.;Narayanasamy, Satish
对非托管语言的垃圾收集 (GC) 支持可以减少推理动态对象活动性时的编程负担。它还避免了临时内存安全违规和内存泄漏。然而，针对 C/C++ 等弱类型语言的 SoundGC 仍然是一个未解决的问题。当前基于值的 GC 解决方案检查内存位置的值以发现指针及其指向的对象。在存在任意类型转换和指针操作的情况下，该方法本质上是不合理的，而这在 C/C++ 中是合法的。这些语言特性经常被使用，特别是在低级系统代码中。在本文中，我们提出动态指针来源跟踪来实现声音GC。我们观察到指针不能凭空创建，并且它们必须具有至少一个有效分配的来源。因此，通过显式数据流和隐式控制流跟踪源头（例如 malloc）的指针来源，我们的 GC 拥有可靠且精确的信息来计算任何程序状态下所有可到达对象的集合。我们讨论了几种静态分析优化，这些优化可以在编译期间使用分析辅助，对于遵守 C 标准的行为良好的程序，将动态来源跟踪的开销从近 8 倍显着降低到 16%。与不健全的基于值的 GC 相比，基于指针来源的健全 GC 调用速度也快了 13%，平均回收的内存多了 6%。
Garbage collection (GC) support for unmanaged languages can reduce programming burden in reasoning about liveness of dynamic objects. It also avoids temporal memory safety violations and memory leaks.SoundGC for weakly-typed languages such as C/C++, however, remains an unsolved problem. Current value-based GC solutions examine values of memory locations to discover the pointers, and the objects they point to. The approach is inherently unsound in the presence of arbitrary type casts and pointer manipulations, which are legal in C/C++. Such language features are regularly used, especially in low-level systems code.In this paper, we propose Dynamic Pointer Provenance Tracking to realize sound GC. We observe that pointers cannot be created out-of-thin-air, and they must have provenance to at least one valid allocation. Therefore, by tracking pointer provenance from the source (e.g., malloc) through both explicit data-flow and implicit control-flow, our GC has sound and precise information to compute the set of all reachable objects at any program state. We discuss several static analysis optimizations, that can be employed during compilation aided with profiling, to significantly reduce the overhead of dynamic provenance tracking from nearly 8× to 16% for well-behaved programs that adhere to the C standards. Pointer provenance based sound GC invocation is also 13% faster and reclaims 6% more memory on average, compared to an unsound value-based GC.
登录
查看更多内容
DOI：
10.1145/3192366.3192376
发表时间：
2018-06
期刊：
Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
J. Vilk;E. Berger
通讯作者：
J. Vilk;E. Berger
乐观混合分析：通过预测静态分析加速动态分析
DOI：
10.1145/3173162.3177153
发表时间：
2018
期刊：
Architectural Support for Programming Languages and Operating Systems
影响因子：
--
作者：
Devecsery, David;Chen, Peter M.;Flinn, Jason;Narayanasamy, Satish
通讯作者：
Narayanasamy, Satish
DOI：
10.1145/3297858.3304017
发表时间：
2019-04
期刊：
Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems
影响因子：
--
作者：
T. Zhang;Dongyoon Lee;Changhee Jung
通讯作者：
T. Zhang;Dongyoon Lee;Changhee Jung
在不合作的环境中增量、分代复制垃圾收集
DOI：
--
发表时间：
1999
期刊：
影响因子：
--
作者：
G. Yip;D. Gifford;J. Bartlett;Vi;Joel F Bartlett Title
通讯作者：
Joel F Bartlett Title
C 中的动态存储回收
DOI：
--
发表时间：
1990
期刊：
影响因子：
--
作者：
Daniel R. Edelson
通讯作者：
Daniel R. Edelson