Precise garbage collection for C

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 W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 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.
• 4: Steven J. Beaty, A technique for tracing memory leaks in C++, ACM SIGPLAN OOPS Messenger, v.5 n.3, p.17-26, July 1994 [doi>10.1145/181904.181907]
• 6: CILBerkeley. CIL. http://manju.cs.berkeley.edu/cil/, 2005.
• 7: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 8: Hans-Juergen Boehm, Space efficient conservative garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.197-206, June 21-25, 1993, Albuquerque, New Mexico, United States
• 9: Hans-J. Boehm, Bounding space usage of conservative garbage collectors, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-100, January 16-18, 2002, Portland, Oregon
• 10: H Bromley, Lisp lore: a guide to programming the Lisp machine, Kluwer Academic Publishers, Norwell, MA, 1986
• 11: William D. Clinger, Proper tail recursion and space efficiency, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.174-185, June 17-19, 1998, Montreal, Quebec, Canada
• 12: Dinakar Dhurjati , Sumant Kowshik , Vikram Adve , Chris Lattner, Memory safety without runtime checks or garbage collection, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 13: Chen Ding , Yutao Zhong, Compiler-directed run-time monitoring of program data access, Proceedings of the 2002 workshop on Memory system performance, p.1-12, June 16-16, 2002, Berlin, Germany
• 14: Nurit Dor , Michael Rodeh , Mooly Sagiv, Detecting memory errors via static pointer analysis (preliminary experience), Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.27-34, June 16-16, 1998, Montreal, Quebec, Canada
• 15: Dawson Engler , Benjamin Chelf , Andy Chou , Seth Hallem, Checking system rules using system-specific, programmer-written compiler extensions, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.1-1, October 22-25, 2000, San Diego, California
• 16: David Evans, Static detection of dynamic memory errors, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.44-53, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 17: Benjamin Goldberg, Tag-free garbage collection for strongly typed programming languages, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.165-176, June 24-28, 1991, Toronto, Ontario, Canada
• 18: David L. Heine , Monica S. Lam, A practical flow-sensitive and context-sensitive C and C++ memory leak detector, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 19: Fergus Henderson, Accurate garbage collection in an uncooperative environment, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 20: Martin Hirzel , Amer Diwan , Johannes Henkel, On the usefulness of type and liveness accuracy for garbage collection and leak detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.593-624, November 2002 [doi>10.1145/586088.586089]
• 21: HnxGC. HnxGC, 2009. http://hnxgc.harnixworld.com/.
• 22: Galen C. Hunt , James R. Larus, Singularity: rethinking the software stack, ACM SIGOPS Operating Systems Review, v.41 n.2, p.37-49, April 2007 [doi>10.1145/1243418.1243424]
• 23: Trevor Jim , J. Greg Morrisett , Dan Grossman , Michael W. Hicks , James Cheney , Yanling Wang, Cyclone: A Safe Dialect of C, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.275-288, June 10-15, 2002
• 24: Dong-Heon Jung , Sung-Hwan Bae , Jaemok Lee , Soo-Mook Moon , JongKuk Park, Supporting precise garbage collection in Java Bytecode-to-C ahead-of-time compiler for embedded systems, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176767]
• 25: phManaged Extensions for C++ Programming. Microsoft, 2004.
• 26: George C. Necula , Scott McPeak , Westley Weimer, CCured: type-safe retrofitting of legacy code, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.128-139, January 16-18, 2002, Portland, Oregon
• 27: Scott M. Pike, Bruce W. Weide, and Joseph E. Hollingsworth. Checkmate: cornering C
• 28: Scott M. Pike , Bruce W. Weide , Joseph E. Hollingsworth, Checkmate: cornering C++ dynamic memory errors with checked pointers, Proceedings of the thirty-first SIGCSE technical symposium on Computer science education, p.352-356, March 07-12, 2000, Austin, Texas, United States
• 29: Gustavo Rodriguez-Rivera , Michael Spertus , Charles Fiterman, A non-fragmenting non-moving, garbage collector, Proceedings of the 1st international symposium on Memory management, p.79-85, October 17-19, 1998, Vancouver, British Columbia, Canada
• 30: Ruby. Ruby, 2008. http://www.ruby-lang.org/.
• 31: John D. Slingwine and Paul E. McKenney, 1995. Patent No. 5,442,758.
• 32: Frederick Smith , Greg Morrisett, Comparing mostly-copying and mark-sweep conservative collection, Proceedings of the 1st international symposium on Memory management, p.68-78, October 17-19, 1998, Vancouver, British Columbia, Canada
• 33: Jan Sparud, Fixing some space leaks without a garbage collector, Proceedings of the conference on Functional programming languages and computer architecture, p.117-122, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165196]
• 34: Sun Microsystems, Inc. JavaOS: A standalone Java environment, 1997. http://www.javasoft.com/products/javaos/javaos.white.html.
• 35: User Mode Linux, 2008. http://user-mode-linux.sourceforge.net/.
• 36: Adam Wick , Matthew Flatt, Magpie: precise garbage collection for c, University of Utah, Salt Lake City, UT, 2006
• 37: Adam Wick , Matthew Flatt, Memory accounting without partitions, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029888]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Design, Reliability

Keywords:
accurate, c programming language, conservative, garbage collection, precise