research-article

Precise garbage collection for C

Authors:

Matthew FlattAuthors Info & Claims

ISMM '09: Proceedings of the 2009 international symposium on Memory management

Pages 39 - 48

https://doi.org/10.1145/1542431.1542438

Published: 19 June 2009 Publication History

Abstract

Magpie is a source-to-source transformation for C programs that enables precise garbage collection, where precise means that integers are not confused with pointers, and the liveness of a pointer is apparent at the source level. Precise GC is primarily useful for long-running programs and programs that interact with untrusted components. In particular, we have successfully deployed precise GC in the C implementation of a language run-time system that was originally designed to use conservative GC. We also report on our experience in transforming parts of the Linux kernel to use precise GC instead of manual memory management.

References

[1]

Andrew Appel. Compiling with Continuations. Cambridge University Press, 1992.

Digital Library

[2]

Todd M. Austin, Scott E. Breach, and Gurindar S. Sohi. Efficient detection of all pointer and array access errors. Technical report, University of Wisconsin-Madison, December 1993.

[3]

Jason Baker, Antonio Cunei, Filip Pizlo, and Jan Vitek. Accurate garbage collection in uncooperative environments with lazy pointer stacks. In Proc. International Conference on Compiler Construction, 2007.

Digital Library

[4]

Steven J. Beaty. A technique for tracing memory leaks in C++. SIGPLAN OOPS Mess., 5 (3): 17--26, June 1994.

Digital Library

[5]

CILBerkeley. CIL. http://manju.cs.berkeley.edu/cil/, 2005.

[6]

B. N. Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. Fiuczynski, D. Becker, S. Eggers, and C. Chambers. Extensibility, safety and performance in the SPIN operating system. In phProc. ACM Symp. on Operating Systems Principles, pages 267--284, December 1995.

Digital Library

[7]

H.-J Boehm. Space efficient conservative garbage collection. In Proc. ACM Conf. on Programming Language Design and Implementation, pages 197--206, 2003.

Digital Library

[8]

Hans-J. Boehm. Bounding space usage of conservative garbage collectors. In phProc. ACM Symposium on Principles of Programming Languages, pages 93--100, 2002.

Digital Library

[9]

Hank Bromley. phLisp Lore: A Guide to Programming the Lisp Machine. Kluwer Academic Publishers, 1986.

Digital Library

[10]

William D. Clinger. Proper tail recursion and space efficiency. In Proc. ACM Conf. on Programming Language Design and Implementation, pages 174--185, 1998.

Digital Library

[11]

Dinakar Dhurjati, Sumant Kowshik, Vikram Adve, and Chris Lattner. Memory safety without runtime checks or garbage collection. In Proc. Conference on Languages, Compilers, and Tools for Embedded Systems, pages 69--80, 2003.

Digital Library

[12]

Chen Ding and Yutao Zhong. Compiler-directed run-time monitoring of program data access. In Proc. of the Workshop on Memory System Performance, pages 1--12. ACM Press, 2002.

Digital Library

[13]

Nurit Dor, Michael Rodeh, and Mooly Sagiv. Detecting memory errors via static pointer analysis (preliminary experience). In Proc. Workshop on Program Analysis for Software Tools and Engineering, pages 27--34. ACM Press, 1998.

Digital Library

[14]

Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proc. ACM Symp. on Operating Systems Design and Implementation, 2000.

Digital Library

[15]

David Evans. Static detection of dynamic memory errors. In Proc. ACM Conf. on Programming Language Design and Implementation, pages 44--53. ACM Press, 1996.

Digital Library

[16]

Benjamin Goldberg. Tag-free garbage collection for strongly typed programming languages. In phProc. ACM Conf. on Programming Language Design and Implementation, pages 165--176, 1991.

Digital Library

[17]

David L. Heine and Monica S. Lam. A practical flow-sensitive and context-sensitive C and C++ memory leak detector. In Proc. ACM Conf. on Programming Language Design and Implementation, pages 168--181. ACM Press, 2003.

Digital Library

[18]

Fergus Henderson. Accurate garbage collection in an uncooperative environment. In Proc. ACM International Symposium on Memory Management, pages 150--156. ACM Press, 2002.

Digital Library

[19]

Martin Hirzel, Amer Diwan, and Johannes Henkel. On the usefulness of type and liveness accuracy for garbage collection and leak detection. ACM Trans. Program. Lang. Syst., 24 (6): 593--624, 2002.

Digital Library

[20]

HnxGC. HnxGC, 2009. http://hnxgc.harnixworld.com/.

[21]

Galen C. Hunt and James R. Larus. Singularity: Rethinking the software stack. ACM SIGOPS Operating Systems Review, 41 (2): 37--49, 2007.

Digital Library

[22]

Trevor Jim, Greg Morrisett, Dan Grossman, Michael Hicks, James Cheney, and Yanling Wang. Cyclone: A safe dialect of C. In Proc. USENIX Annual Technical Conference, pages 275--288, 2002.

Digital Library

[23]

Dong-Heon Jung, Sung-Hwan Bae, Jaemok Lee, Soo-Mook Moon, and JongKuk Park. Supporting precise garbage collection in Java bytecode-to-C ahead-of-time compiler for embedded systems. In roc. International Conference on Compilers, Architecture and Synthesis for Embedded Systems, pages 35--42, 2006.

Digital Library

[24]

phManaged Extensions for C++ Programming. Microsoft, 2004.

[25]

George C. Necula, Scott McPeak, and Westley Weimer. Ccured: type-safe retrofitting of legacy code. In phProc. ACM Symposium on Principles of Programming Languages, pages 128--139, 2002.

Digital Library

[26]

Scott M. Pike, Bruce W. Weide, and Joseph E. Hollingsworth. Checkmate: cornering C

[27]

dynamic memory errors with checked pointers. In Proc. SIGCSE Technical Symposium on Computer Science Education, pages 352--356. ACM Press, 2000.

Digital Library

[28]

Gustavo Rodriguez-Rivera, Michael Spertus, and Charles Fiterman. A non-fragmenting non-moving, garbage collector. In Proc. ACM International Symposium on Memory Management, pages 79--85. ACM Press, 1998.

Digital Library

[29]

Ruby. Ruby, 2008. http://www.ruby-lang.org/.

[30]

John D. Slingwine and Paul E. McKenney, 1995. Patent No. 5,442,758.

[31]

Frederick Smith and Greg Morrisett. Comparing mostly-copying and mark-sweep conservative collection. In Proc. International Symposium on Memory Management, pages 68--78. ACM Press, 1998.

Digital Library

[32]

Jan Sparud. Fixing some space leaks without a garbage collector. In Proc. Conference on Functional Programming Languages and Computer Architecture, pages 117--122. ACM Press, 1993.

Digital Library

[33]

Sun Microsystems, Inc. JavaOS: A standalone Java environment, 1997. http://www.javasoft.com/products/javaos/javaos.white.html.

[34]

User Mode Linux, 2008. http://user-mode-linux.sourceforge.net/.

[35]

Adam Wick. Magpie: Precise Garbage Collection for C. PhD thesis, University of Utah, June 2006.

Digital Library

[36]

Adam Wick and Matthew Flatt. Memory accounting without partitions. In Proc. ACM International Symposium on Memory Management, 2004.

Digital Library

Cited By

Milburn AVan Der Kouwe EGiuffrida C(2022)Mitigating Information Leakage Vulnerabilities with Type-based Data Isolation2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833675(1049-1065)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833675
Magalhães JLiao CPereira F(2022)Automatic inspection of program state in an uncooperative environmentSoftware: Practice and Experience10.1002/spe.314652:12(2727-2758)Online publication date: 31-Aug-2022
https://doi.org/10.1002/spe.3146
Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Show More Cited By

Index Terms

Precise garbage collection for C
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Fast conservative garbage collection
OOPSLA '14

Garbage collectors are exact or conservative. An exact collector identifies all references precisely and may move referents and update references, whereas a conservative collector treats one or more of stack, register, and heap references as ambiguous. ...
Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISMM '09: Proceedings of the 2009 international symposium on Memory management

June 2009

158 pages

ISBN:9781605583471

DOI:10.1145/1542431

General Chair:
Hillel Kolodner
IBM Haifa Research
,
Program Chair:
Guy Steele
Sun Microsystems Laboratories

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISMM '09

Sponsor:

ISMM '09: International Symposium on Memory Management

June 19 - 20, 2009

Dublin, Ireland

Acceptance Rates

ISMM '09 Paper Acceptance Rate 15 of 32 submissions, 47%;

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
551
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)6

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Milburn AVan Der Kouwe EGiuffrida C(2022)Mitigating Information Leakage Vulnerabilities with Type-based Data Isolation2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833675(1049-1065)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833675
Magalhães JLiao CPereira F(2022)Automatic inspection of program state in an uncooperative environmentSoftware: Practice and Experience10.1002/spe.314652:12(2727-2758)Online publication date: 31-Aug-2022
https://doi.org/10.1002/spe.3146
Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Cutler CKaashoek MMorris RArpaci-Dusseau AVoelker G(2018)The benefits and costs of writing a POSIX kernel in a high-level languageProceedings of the 13th USENIX conference on Operating Systems Design and Implementation10.5555/3291168.3291176(89-105)Online publication date: 8-Oct-2018
https://dl.acm.org/doi/10.5555/3291168.3291176
Tripp CHyde DGrossman-Ponemon B(2018)FRC: a high-performance concurrent parallel deferred reference counter for C++ACM SIGPLAN Notices10.1145/3299706.321056953:5(14-28)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3299706.3210569
van der Kouwe EKroes TOuwehand CBos HGiuffrida C(2018)Type-After-TypeProceedings of the 34th Annual Computer Security Applications Conference10.1145/3274694.3274705(17-27)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.1145/3274694.3274705
Tripp CHyde DGrossman-Ponemon BPayer HSartor J(2018)FRC: a high-performance concurrent parallel deferred reference counter for C++Proceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management10.1145/3210563.3210569(14-28)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3210563.3210569
Silvestro SLiu HCrosser CLin ZLiu TThuraisingham BEvans DMalkin TXu D(2017)FreeGuardProceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security10.1145/3133956.3133957(2389-2403)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.1145/3133956.3133957
Kell STorlak EStorm TBiddle R(2017)Some were meant for C: the endurance of an unmanageable languageProceedings of the 2017 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3133850.3133867(229-245)Online publication date: 25-Oct-2017
https://dl.acm.org/doi/10.1145/3133850.3133867
Rigger MSchatz RGrimmer MMössenböck H(2017)Lenient Execution of C on a Java Virtual MachineProceedings of the 14th International Conference on Managed Languages and Runtimes10.1145/3132190.3132204(35-47)Online publication date: 27-Sep-2017
https://dl.acm.org/doi/10.1145/3132190.3132204
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents