Bell: bit-encoding online memory leak detection

ABSTRACT

Memory leaks compromise availability and security by crippling performance and crashing programs. Leaks are difficult to diagnose because they have no immediate symptoms. Online leak detection tools benefit from storing and reporting per-object sites (e.g., allocation sites) for potentially leaking objects. In programs with many small objects, per-object sites add high space overhead, limiting their use in production environments.This paper introduces Bit-Encoding Leak Location (Bell), a statistical approach that encodes per-object sites to a single bit per object. A bit loses information about a site, but given sufficient objects that use the site and a known, finite set of possible sites, Bell uses brute-force decoding to recover the site with high accuracy.We use this approach to encode object allocation and last-use sites in Sleigh, a new leak detection tool. Sleigh detects stale objects (objects unused for a long time) and uses Bell decoding to report their allocation and last-use sites. Our implementation steals four unused bits in the object header and thus incurs no per-object space overhead. Sleigh's instrumentation adds 29% execution time overhead, which adaptive profiling reduces to 11%. Sleigh's output is directly useful for finding and fixing leaks in SPEC JBB2000 and Eclipse, although sufficiently many objects must leak before Bell decoding can report sites with confidence. Bell is suitable for other leak detection approaches that store per-object sites, and for other problems amenable to statistical per-object metadata.

REFERENCES

• 1: 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
• 2: BEA. JRockit. http://dev2dev.bea.com/jrockit/.
• 3: BEA. JRockit Mission Control. http://dev2dev.bea.com/jrockit/-tools.html.
• 4: Emery D. Berger , Benjamin G. Zorn , Kathryn S. McKinley, Reconsidering custom memory allocation, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 5: 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
• 6: 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 , 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
• 7: 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]
• 8: Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.159-170, June 20-24, 1994, Orlando, Florida, United States
• 9: CERT/CC. CERT/CC Advisories. http://www.cert.org/advisories/.
• 10: 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
• 11: Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
• 12: Commons-Math: The Jakarta Mathematics Library. http://jakarta.-apache.org/commons/math/.
• 13: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 14: Sylvia Dieckmann , Urs Hölzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmark, Proceedings of the 13th European Conference on Object-Oriented Programming, p.92-115, June 14-18, 1999
• 15: Eclipse.org Home. http://www.eclipse.org/.
• 16: J. Fenn and A. Linden. Hype Cycle Special Report for 2005. Gartner Group.
• 17: N. Grcevski, A. Kielstra, K. Stoodley, M. G. Stoodley, and V. Sundaresan. Java Just-in-Time Compiler and Virtual Machine Improvements for Server and Middleware Applications. In Virtual Machine Research and Technology Symposium, pages 151--162, 2004.
• 18: R. Hastings and B. Joyce. Purify: Fast Detection of Memory Leaks and Access Errors. In Winter USENIX Conference, pages 125--136, 1992.
• 19: 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
• 20: Jikes RVM Research Archive. http://jikesrvm.sourceforge.net/info/-research-archive.shtml.
• 21: Maria Jump , Stephen M. Blackburn , Kathryn S. McKinley, Dynamic object sampling for pretenuring, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029892]
• 22: M. Jump and K.S. McKinley. Cork: Dynamic Memory Leak Detection for Java. Technical Report TR-06-07, The University of Texas at Austin, 2006. Under submission.
• 23: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 24: 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.
• 25: N. Nethercote and J. Seward. Valgrind: A Program Supervision Framework. Electronic Notes in Theoretical Computer Science, 89(2), 2003.
• 26: 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]
• 27: Quest. JProbe Memory Debugger. http://www.quest.com/jprobe/-debugger.asp.
• 28: SciTech Software. .NET Memory Profiler. http://www.scitech.se/-memprofiler/.
• 29: D. Scott. Assessing the Costs of Application Downtime. Gartner Group, 1998.
• 30: Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, 1999.
• 31: Standard Performance Evaluation Corporation. SPECjbb2000 Documentation, release 1.01 edition, 2001.
• 32: US-CERT. US-CERT Vulnerability Notes Database. http://www.kb.cert.org/vuls/.
• 33: 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.4 Software/Program Verification
          Subjects: Reliability

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods

General Terms:
Experimentation, Performance, Reliability

Keywords:
low-overhead monitoring, managed languages, memory leaks, probabilistic approaches