Safe manual memory management

ABSTRACT

We present HeapSafe, a tool that uses reference counting to dynamically verify the soundness of manual memory management of C programs. HeapSafe relies on asimple extension to the usual malloc/free memory management API: delayed free scopes during which otherwise dangling references can exist. Porting programs for use with HeapSafe typically requires little effort (on average 0.6% oflines change), adds an average 11% time overhead (84% in the worst case), and increases space usage by an average of 13%. These results are based on portingover half a million lines of C code, including perl where we found sixpreviously unknown bugs.Many existing C programs continue to use unchecked manual memorymanagement. One reason is that programmers fear that moving to garbage collection is too big a risk. We believe that HeapSafe is a practical way toprovide safe memory management for such programs. Since HeapSafe checks existing memory management rather than changing it, programmers need not worrythat HeapSafe will introduce new bugs; and, since HeapSafe does not managememory itself, programmers can choose to deploy their programs without HeapSafe if performance is critical (a simple header file allows HeapSafe programs to compile and run with a regular C compiler). In contrast, we foundthat garbage collection, although faster, had much higher space overhead, and occasionally caused a space-usage explosion that made the program unusable.

REFERENCES

• 1: Zachary Anderson , Eric Brewer , Jeremy Condit , Robert Ennals , David Gay , Matthew Harren , George C. Necula , Feng Zhou, Beyond bug-finding: sound program analysis for Linux, Proceedings of the 11th USENIX workshop on Hot topics in operating systems, p.1-6, May 07-09, 2007, San Diego, CA
• 2: APPLE. Cocoa. http://developer.apple.com.
• 3: Todd M. Austin , Scott E. Breach , Gurindar S. Sohi, Efficient detection of all pointer and array access errors, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.290-301, June 20-24, 1994, Orlando, Florida, United States
• 4: David F. Bacon , V. T. Rajan, Concurrent Cycle Collection in Reference Counted Systems, Proceedings of the 15th European Conference on Object-Oriented Programming, p.207-235, June 18-22, 2001
• 5: Emery David Berger , Kathryn S. Mckinley, Memory management for high-performance applications, The University of Texas at Austin, 2002
• 6: Daniel G. Bobrow, Managing Reentrant Structures Using Reference Counts, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.269-273, July 1980 [doi>10.1145/357103.357104]
• 7: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 8: CONDIT, J., HARREN, M., ANDERSON, Z., GAY, D., AND NECULA, G. Dependent types for low--level programming. In ESOP-07.
• 9: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 10: Dinakar Dhurjati , Vikram Adve, Backwards-compatible array bounds checking for C with very low overhead, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134309]
• 11: Dinakar Dhurjati , Sumant Kowshik , Vikram Adve , Chris Lattner, Memory safety without garbage collection for embedded applications, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.73-111, February 2005 [doi>10.1145/1053271.1053275]
• 12: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 13: 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
• 14: C. N. Fischer , R. J. LeBlanc, The Implementation of Run-Time Diagnostics in Pascal, IEEE Transactions on Software Engineering, v.6 n.4, p.313-319, July 1980 [doi>10.1109/TSE.1980.230482]
• 15: David Gay , Alex Aiken, Language support for regions, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.70-80, June 2001, Snowbird, Utah, United States
• 16: 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
• 17: JONES, R., AND LINS, R. Garbage Collection. Wiley, 1996.
• 18: JONES, R. W. M., AND KELLY, P. H. J. Backwards compatible bounds checking for arrays and pointers in C. In Automated and Algorithmic Debugging (AADEBUG--97) (1997).
• 19: Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.367-380, October 14-18, 2001, Tampa Bay, FL, USA
• 20: Alexey Loginov , Suan Hsi Yong , Susan Horwitz , Thomas W. Reps, Debugging via Run-Time Type Checking, Proceedings of the 4th International Conference on Fundamental Approaches to Software Engineering, p.217-232, April 02-06, 2001
• 21: LOMET, D. B. Making pointers safe in system programming languages. IEEE Transactions on Software Engineering SE-- 11, 1 (Jan. 1985), 87--96.
• 22: George C. Necula , Jeremy Condit , Matthew Harren , Scott McPeak , Westley Weimer, CCured: type-safe retrofitting of legacy software, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.477-526, May 2005 [doi>10.1145/1065887.1065892]
• 23: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 24: NEXT. Openstep. http://www.gnustep.org.
• 25: Harish Patil , Charles Fischer, Low-cost, concurrent checking of pointer and array accesses in C programs, Software—Practice & Experience, v.27 n.1, p.87-110, Jan. 1997 [doi>10.1002/(SICI)1097-024X(199701)27:1<87::AID-SPE78>3.0.CO;2-P ]
• 26: PERENS, B. Electric fence. http://perens.com/FreeSoftware/.
• 27: RATIONAL SOFTWARE. Purify: Fast detection of memory leaks and access errors. http://www.rational.com.
• 28: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 29: Julian Seward , Nicholas Nethercote, Using Valgrind to detect undefined value errors with bit-precision, Proceedings of the annual conference on USENIX Annual Technical Conference, p.2-2, April 10-15, 2005, Anaheim, CA
• 30: SPEC. SPECCPU 2000 and 2006. http://www.spec.org.
• 31: WATSON, G. Dmalloc -- debug malloc. http://dmalloc.com.
• 32: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 33: ZORN, B. The measured cost of conservative garbage collection. Tech. Rep. CU--CS--573--92, University of Colorado at Boulder, April 1992.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Keywords:
C, memory management, reference counting, safety