Tolerating memory leaks

ABSTRACT

Type safety and garbage collection in managed languages eliminate memory errors such as dangling pointers, double frees, and leaks of unreachable objects. Unfortunately, a program still leaks memory if it maintains references to objects it will never use again. Leaked objects decrease program locality and increase garbage collection frequency and workload. A growing leak will eventually exhaust memory and crash the program.

This paper introduces a leak tolerance approach called Melt that safely eliminates performance degradations and crashes due to leaks of dead but reachable objects in managed languages, given sufficient disk space to hold leaking objects. Melt (1) identifies stale objects that the program is not accessing; (2) segregates in-use and stale objects by storing stale objects to disk; and (3) preserves safety by activating stale objects if the program subsequently accesses them. We design and build a prototype implementation of Melt in a Java VM and show it adds overhead low enough for production systems. Whereas existing VMs grind to a halt and then crash on programs with leaks, Melt keeps many of these programs running much longer without significantly degrading performance. Melt provides users the illusion of a fixed leak and gives developers more time to fix leaky programs.

REFERENCES

• 1: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 2: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 3: M. P. Atkinson , L. Daynès , M. J. Jordan , T. Printezis , S. Spence, An orthogonally persistent Java, ACM SIGMOD Record, v.25 n.4, p.68-75, Dec. 1996 [doi>10.1145/245882.245905]
• 4: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-298, January 15-17, 2003, New Orleans, Louisiana, USA
• 5: Emery D. Berger , Benjamin G. Zorn, DieHard: probabilistic memory safety for unsafe languages, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 6: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
• 7: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 8: Stephen M. Blackburn , Antony L. Hosking, Barriers: friend or foe?, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029891]
• 9: Michael D. Bond , Kathryn S. McKinley, Bell: bit-encoding online memory leak detection, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 10: M. D. Bond and K. S. McKinley. Tolerating Memory Leaks. Technical Report TR-07-64, University of Texas at Austin, December 2007.
• 11: D. Breitgand, M. Goldstein, E. Henis, O. Shehory, and Y. Weinsberg. PANACEA-Towards a Self-Healing Development Framework. In Integrated Network Management, pages 169--178, 2007.
• 12: G. Chen , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , B. Mathiske , M. Wolczko, Heap compression for memory-constrained Java environments, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 13: Wen-ke Chen , Sanjay Bhansali , Trishul Chilimbi , Xiaofeng Gao , Weihaw Chuang, Profile-guided proactive garbage collection for locality optimization, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 14: Sigmund Cherem , Lonnie Princehouse , Radu Rugina, Practical memory leak detection using guarded value-flow analysis, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 15: Matthias Hauswirth , Trishul M. Chilimbi, Low-overhead memory leak detection using adaptive statistical profiling, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 16: DaCapo Benchmark Regression Tests. http://jikesrvm.anu.-edu.au/?dacapo/.
• 17: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 18: Eclipse.org Home. http://www.eclipse.org/.
• 19: B. Goetz. Plugging memory leaks with weak references, 2005. http://www-128.ibm.com/developerworks/java/-library/j-jtp11225/.
• 20: B. Goetz. Plugging memory leaks with soft references, 2006. http://www-128.ibm.com/developerworks/java/-library/j-jtp01246.html.
• 21: Maayan Goldstein , Onn Shehory , Yaron Weinsberg, Can self-healing software cope with loitering?, Fourth international workshop on Software quality assurance: in conjunction with the 6th ESEC/FSE joint meeting, September 03-04, 2007, Dubrovnik, Croatia [doi>10.1145/1295074.1295076]
• 22: Leonidas J. Guibas , Donald E. Knuth , Micha Sharir, Randomized Incremental Construction of Delaunay and Voronoi Diagrams, Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.414-431, July 16-20, 1990
• 23: S. C. Gupta and R. Palanki. Java memory leaks -- Catch me if you can, 2005. http://www.ibm.com/developerworks/-rational/library/05/0816 GuptaPalanki/index.html.
• 24: R. Hastings and B. Joyce. Purify: Fast Detection of Memory Leaks and Access Errors. In Winter USENIX Conference, pages 125--136, 1992.
• 25: 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
• 26: Matthew Hertz , Yi Feng , Emery D. Berger, Garbage collection without paging, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 27: 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]
• 28: Antony L. Hosking , Jiawan Chen, PM3: An Orthogonal Persistent Systems Programming Language - Design, Implementation, Performance, Proceedings of the 25th International Conference on Very Large Data Bases, p.587-598, September 07-10, 1999
• 29: Antony L. Hosking , J. Eliot B. Moss, Object fault handling for persistent programming languages: a performance evaluation, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.288-303, September 26-October 01, 1993, Washington, D.C., United States
• 30: Antony L. Hosking , Nathaniel Nystrom , Quintin I. Cutts , Kumar Brahnmath, Optimizing the Read and Write Barriers for Orthogonal Persistence, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3): Advances in Persistent Object Systems, p.149-159, January 1999
• 31: Xianglong Huang , Stephen M. Blackburn , Kathryn S. McKinley , J Eliot B. Moss , Zhenlin Wang , Perry Cheng, The garbage collection advantage: improving program locality, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 32: Jikes RVM. http://www.jikesrvm.org.
• 33: Jikes RVM Research Archive. http://www.jikesrvm.org/-Research+Archive.
• 34: Maria Jump , Kathryn S. McKinley, Cork: dynamic memory leak detection for garbage-collected languages, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 35: J.Maebe, M. Ronsse, and K. D. Bosschere. Precise Detection of Memory Leaks. In International Workshop on Dynamic Analysis, pages 25--31, 2004.
• 36: Alonso Marquez , Stephen Blackburn , Gavin Mercer , John N. Zigman, Implementing Orthogonally Persistent Java, Revised Papers from the 9th International Workshop on Persistent Object Systems, p.247-261, September 06-08, 2000
• 37: Mckoi SQL Database message board: memory/thread leak with Mckoi 0.93 in embedded mode, 2002. http://www.-mckoi.com/database/mail/subject.jsp?id=2172.
• 38: N. Mitchell and G. Sevitsky. LeakBot: An Automated and Lightweight Tool for Diagnosing Memory Leaks in Large Java Applications. In European Conference on Object-Oriented Programming, pages 351--377, 2003.
• 39: J. Eliot B. Moss, Working with Persistent Objects: To Swizzle or Not to Swizzle, IEEE Transactions on Software Engineering, v.18 n.8, p.657-673, August 1992 [doi>10.1109/32.153378]
• 40: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 41: Huu Hai Nguyen , Martin Rinard, Detecting and eliminating memory leaks using cyclic memory allocation, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296912]
• 42: G. Novark, E. D. Berger, and B. G. Zorn. Plug: Automatically Tolerating Memory Leaks in C and C++ Applications. Technical Report UM-CS-2008-009, University of Massachusetts, 2008.
• 43: Kazunori Ogata , Tamiya Onodera , Kiyokuni Kawachiya , Hideaki Komatsu , Toshio Nakatani, Replay compilation: improving debuggability of a just-in-time compiler, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 44: Oracle. JRockit Mission Control. http://www.oracle.com/-technology/products/jrockit/missioncontrol/.
• 45: Filip Pizlo , Daniel Frampton , Erez Petrank , Bjarne Steensgaard, Stopless: a real-time garbage collector for multiprocessors, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296927]
• 46: D. Plainfossé. Distributed Garbage Collection and Reference Management in the Soul Object Support System. PhD thesis, Université Paris-6, Pierre-et-Marie-Curie, 1994.
• 47: Feng Qin , Shan Lu , Yuanyuan Zhou, SafeMem: Exploiting ECC-Memory for Detecting Memory Leaks and Memory Corruption During Production Runs, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.291-302, February 12-16, 2005 [doi>10.1109/HPCA.2005.29]
• 48: Feng Qin , Joseph Tucek , Jagadeesan Sundaresan , Yuanyuan Zhou, Rx: treating bugs as allergies---a safe method to survive software failures, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 49: Quest. JProbe Memory Debugger. http://www.quest.com/-jprobe/debugger.asp.
• 50: Martin Rinard , Cristian Cadar , Daniel Dumitran , Daniel M. Roy , Tudor Leu , William S. Beebee, Jr., Enhancing server availability and security through failure-oblivious computing, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.21-21, December 06-08, 2004, San Francisco, CA
• 51: Narendran Sachindran , J. Eliot B. Moss , Emery D. Berger, MC²: high-performance garbage collection for memory-constrained environments, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 52: SciTech Software. .NET Memory Profiler. http://www.-scitech.se/memprofiler/.
• 53: Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, 1999.
• 54: Standard Performance Evaluation Corporation. SPECjbb2000 Documentation, release 1.01 edition, 2001.
• 55: Sun Developer Network Forum. Java Programming {Archive} - garbage collection dilema (sic), 2003. http://forum.java.-sun.com/thread.jspa?threadID=446934.
• 56: Sun Developer Network Forum. Reflections & Reference Objects - Java memory leak example, 2003. http://forum.-java.sun.com/thread.jspa?threadID=456545.
• 57: Yan Tang , Yan Tang , Qi Gao , Qi Gao , Feng Qin , Feng Qin, LeakSurvivor: towards safely tolerating memory leaks for garbage-collected languages, USENIX 2008 Annual Technical Conference on Annual Technical Conference, p.307-320, June 22-27, 2008, Boston, Massachusetts
• 58: Paul R. Wilson, Pointer swizzling at page fault time: efficiently supporting huge address spaces on standard hardware, ACM SIGARCH Computer Architecture News, v.19 n.4, p.6-13, June 1991 [doi>10.1145/122576.122577]
• 59: Feng Xian , Witawas Srisa-an , Hong Jiang, Microphase: an approach to proactively invoking garbage collection for improved performance, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 60: Ting Yang , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, CRAMM: virtual memory support for garbage-collected applications, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 61: Ting Yang , Matthew Hertz , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, Automatic heap sizing: taking real memory into account, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029881]
• 62: John N. Zigman , Stephen Blackburn , J. Eliot B. Moss, TMOS: A Transactional Garbage Collector, Revised Papers from the 9th International Workshop on Persistent Object Systems, p.138-156, September 06-08, 2000
• 63: B. Zorn. Barrier Methods for Garbage Collection. Technical Report CU-CS-494-90, University of Colorado at Boulder, 1990.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery

General Terms:
Experimentation, Performance, Reliability

Keywords:
bug tolerance, managed languages, memory leaks