research-article

Efficiently and precisely locating memory leaks and bloat

Authors:

Emery D. Berger,

Benjamin G. ZornAuthors Info & Claims

PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 397 - 407

https://doi.org/10.1145/1542476.1542521

Published: 15 June 2009 Publication History

Abstract

Inefficient use of memory, including leaks and bloat, remain a significant challenge for C and C++ developers. Applications with these problems become slower over time as their working set grows and can become unresponsive. At the same time, memory leaks and bloat remain notoriously difficult to debug, and comprise a large number of reported bugs in mature applications. Previous tools for diagnosing memory inefficiencies-based on garbage collection, binary rewriting, or code sampling-impose high overheads (up to 100X) or generate many false alarms.

This paper presents Hound, a runtime system that helps track down the sources of memory leaks and bloat in C and C++ applications. Hound employs data sampling, a staleness-tracking approach based on a novel heap organization, to make it both precise and efficient. Hound has no false positives, and its runtime and space overhead are low enough that it can be used in deployed applications. We demonstrate Hound's efficacy across a suite of synthetic benchmarks and real applications.

References

[1]

A. W. Appel and K. Li. Virtual memory primitives for user programs. In Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '91), pages 96--107, 1991.

Digital Library

[2]

E. D. Berger, B. G. Zorn, and K. S. McKinley. Reconsidering custom memory allocation. In Proceedings of the 2002 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA '02), pages 1--12, 2002.

Digital Library

[3]

M. D. Bond and K. S. McKinley. Bell: bit-encoding online memory leak detection. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '06), pages 61--72, San Jose, CA, Oct. 2006.

Digital Library

[4]

M. D. Bond and K. S. McKinley. Tolerating memory leaks. In Proceedings of the 23rd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2008), pages 109--126, Nashville, TN, Oct. 2008. ACM.

Digital Library

[5]

S. Cherem, L. Princehouse, and R. Rugina. Practical memory leak detection using guarded value-flow analysis. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming language design and implementation (PLDI '07), pages 480--491, 2007.

Digital Library

[6]

D. Dhurjati and V. Adve. Efficiently detecting all dangling pointer uses in production servers. In Proceedings of the International Conference on Dependable Systems and Networks (DSN '06), pages 269--280, Washington, DC, USA, 2006. IEEE Computer Society.

Digital Library

[7]

R. Hastings and B. Joyce. Fast detection of memory leaks and access errors. In Proceedings of the Winter '92 USENIX conference, pages 125--136. USENIX Association, 1992.

[8]

M. Hauswirth and T. M. Chilimbi. Low-overhead memory leak detection using adaptive statistical profiling. In ASPLOS, pages 156--164, Boston, MA, Apr. 2004. ACM.

Digital Library

[9]

D. L. Heine and M. S. Lam. A practical flow-sensitive and context-sensitive C and C++ memory leak detector. In Proceedings of the ACM SIGPLAN 2003 conference on Programming Language Design and Implementation (PLDI '03), pages 168--181, 2003.

Digital Library

[10]

R. E. Jones and R. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, Chichester, July 1996.

Digital Library

[11]

M. Jump and K. S. McKinley. Cork: Dynamic memory leak detection for garbage-collected languages. In Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages (POPL '07), pages 31--38, 2007.

Digital Library

[12]

P.-H. Kamp. Malloc(3) revisited. http://phk.freebsd.dk/pubs/malloc.pdf.

Digital Library

[13]

C. Lattner and V. Adve. Automatic pool allocation: improving performance by controlling data structure layout in the heap. In PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, pages 129--142, 2005.

Digital Library

[14]

D. Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html, 1997.

[15]

C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. In Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation (PLDI '05), pages 190--200, 2005.

Digital Library

[16]

V. B. Lvin, G. Novark, E. D. Berger, and B. G. Zorn. Archipelago: trading address space for reliability and security. In Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems, (ASPLOS '08), pages 115--124, Mar. 2008.

Digital Library

[17]

J. Maebe, M. Ronsse, and K. D. Bosschere. Precise detection of memory leaks. In Workshop on Dynamic Analysis (WODA 04), pages 25--31, 2004.

[18]

Microsoft TechNet, Microsoft Corporation. Memory Leak Diagnoser, Dec. 2007.

[19]

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 (ECOOP), 2003.

[20]

Mozilla.org. Bugzilla@mozilla, 2008. {Online; accessed 12-March-2008}.

[21]

N. Nethercote and J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. In Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation (PLDI '07), pages 89--100, June 2007.

Digital Library

[22]

H. H. Nguyen and M. Rinard. Detecting and eliminating memory leaks using cyclic memory allocation. In Proceedings of the 6th International Symposium on Memory Management (ISMM '07), pages 15--30, 2007.

Digital Library

[23]

M. Orlovich and R. Rugina. Memory leak analysis by contradiction. In Proceedings of the 13th Annual Static Analysis Symposium (SAS '06), pages 405--424, 2006.

Digital Library

[24]

F. Qin, S. Lu, and Y. Zhou. SafeMem: Exploiting ECC-memory for detecting memory leaks and memory corruption during production runs. In Proceedings of the 11th International Symposium on High-Performance Computer Architecture (HPCA '05), volume 00, pages 291--302. IEEE Computer Society, 2005.

Digital Library

[25]

D. Rayside and L. Mendel. Object ownership profiling: a technique for finding and fixing memory leaks. In Proceedings of the 22nd IEEE/ACM international conference on Automated software engineering (ASE '07), pages 194--203, 2007.

Digital Library

[26]

N. Röjemo and C. Runciman. Lag, drag, void, and use: Heap profiling and space-efficient compilation revisited. In Proceedings of First International Conference on Functional Programming, pages 34--41, Philadelphia, PA, May 1996. ACM Press.

Digital Library

[27]

M. L. Seidl and B. G. Zorn. Segregating heap objects by reference behavior and lifetime. In Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '98), pages 12--23, San Jose, CA, Oct. 1998.

Digital Library

[28]

R. Shaham, E. K. Kolodner, and S. Sagiv. Automatic removal of array memory leaks in Java. In Proceedings of the 9th International Conference on Compiler Construction (CC '00), pages 50--66, London, UK, 2000. Springer.

Digital Library

[29]

R. Shaham, E. Yahav, E. Kolodner, and M. Sagiv. Establishing local temporal heap safety properties with applications to compile-time memory management. In SAS '03: Proceedings of the 10th Annual Static Analysis Symposium, 2003.

Digital Library

[30]

Standard Performance Evaluation Corporation. SPEC2006. http://www.spec.org.

[31]

Y. Tang, Q. Gao, and F. Qin. LeakSurvivor: Towards safely tolerating memory leaks for garbage-collected languages. In Proceedings of the 2008 USENIX Annual Technical Conference (USENIX '08), pages 307--320, Boston, MA, June 2008.

Digital Library

[32]

L. Torvalds. Linux kernel mailing list post. http://lkml.org/lkml/2004/1/12/265, 1 2004.

[33]

T. Tsai, K. Vaidyanathan, and K. C. Gross. Low-overhead run-time memory leak detection and recovery. In Proceedings of the 12th Pacific Rim International Symposium on Dependable Computing (PRDC '06), pages 329--340. IEEE Computer Society, 2006.

Digital Library

[34]

G. Venkataramani, B. Roemer, Y. Solihin, and M. Prvulovic. Memtracker: Efficient and programmable support for memory access monitoring and debugging. In Proceedings of the 13th International Symposium on High-Performance Computer Architecture (HPCA'07), pages 273--284. IEEE Computer Society, 2007.

Digital Library

[35]

P. R. Wilson, M. S. Johnstone, M. Neely, and D. Boles. Dynamic storage allocation: A survey and critical review. In Proceedings of the International Workshop on Memory Management, volume 986, pages 1--116, Kinross, Scotland, Sept. 1995. Springer.

Digital Library

[36]

Y. Xie and A. Aiken. Context-and path-sensitive memory leak detection. In Proceedings of the 5th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESAC/FSE '05), pages 115--125, 2005.

Digital Library

[37]

T. Yang, E. D. Berger, S. F. Kaplan, and J. E. B. Moss. CRAMM: Virtual memory support for garbage-collected applications. In 7th Symposium on Operating Systems Design and Implementation (OSDI'06), pages 103--116. USENIX Association, 2006.

Digital Library

Cited By

Lombardi SSimon TSchwartz GZollhoefer MSheikh YSaragih J(2021)Mixture of volumetric primitives for efficient neural renderingACM Transactions on Graphics10.1145/3450626.345986340:4(1-13)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459863
Martel JLindell DLin CChan EMonteiro MWetzstein G(2021)AcornACM Transactions on Graphics10.1145/3450626.345978540:4(1-13)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459785
Azhari VBhamra SEzzati-Jivan NTetreault F(2021)Efficient heap monitoring tool for memory leak detection and root-cause analysis2021 IEEE International Conference on Big Data (Big Data)10.1109/BigData52589.2021.9671473(3020-3030)Online publication date: 15-Dec-2021
https://doi.org/10.1109/BigData52589.2021.9671473
Show More Cited By

Index Terms

Efficiently and precisely locating memory leaks and bloat
1. Software and its engineering

Recommendations

Automated memory leak detection for production use
ICSE 2014: Proceedings of the 36th International Conference on Software Engineering

This paper presents Sniper, an automated memory leak detection tool for C/C++ production software. To track the staleness of allocated memory (which is a clue to potential leaks) with little overhead (mostly <3%), Sniper leverages instruction sampling ...
Efficiently and precisely locating memory leaks and bloat
PLDI '09

Inefficient use of memory, including leaks and bloat, remain a significant challenge for C and C++ developers. Applications with these problems become slower over time as their working set grows and can become unresponsive. At the same time, memory ...
Diagnosing memory leaks using graph mining on heap dumps
KDD '10: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining

Memory leaks are caused by software programs that prevent the reclamation of memory that is no longer in use. They can cause significant slowdowns, exhaustion of available storage space and, eventually, application crashes. Detecting memory leaks is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2009

492 pages

ISBN:9781605583921

DOI:10.1145/1542476

General Chair:
Michael Hind
IBM Research, USA
,
Program Chair:
Amer Diwan
University of Colorado at Boulder, USA

ACM SIGPLAN Notices Volume 44, Issue 6
PLDI '09
June 2009
478 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1543135
Issue’s Table of Contents

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: 15 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '09

Sponsor:

PLDI '09: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 15 - 21, 2009

Dublin, Ireland

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
993
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)7

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lombardi SSimon TSchwartz GZollhoefer MSheikh YSaragih J(2021)Mixture of volumetric primitives for efficient neural renderingACM Transactions on Graphics10.1145/3450626.345986340:4(1-13)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459863
Martel JLindell DLin CChan EMonteiro MWetzstein G(2021)AcornACM Transactions on Graphics10.1145/3450626.345978540:4(1-13)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459785
Azhari VBhamra SEzzati-Jivan NTetreault F(2021)Efficient heap monitoring tool for memory leak detection and root-cause analysis2021 IEEE International Conference on Big Data (Big Data)10.1109/BigData52589.2021.9671473(3020-3030)Online publication date: 15-Dec-2021
https://doi.org/10.1109/BigData52589.2021.9671473
Atkinson ECarbin M(2020)Programming and reasoning with partial observabilityProceedings of the ACM on Programming Languages10.1145/34282684:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428268
Trinh MChu DJaffar J(2020)Inter-theory dependency analysis for SMT string solversProceedings of the ACM on Programming Languages10.1145/34282604:OOPSLA(1-27)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428260
Stiévenart QMadsen M(2020)Fuzzing channel-based concurrency runtimes using types and effectsProceedings of the ACM on Programming Languages10.1145/34282544:OOPSLA(1-27)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428254
Rouvoet Avan Antwerpen HBach Poulsen CKrebbers RVisser E(2020)Knowing when to ask: sound scheduling of name resolution in type checkers derived from declarative specificationsProceedings of the ACM on Programming Languages10.1145/34282484:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428248
Milanova A(2020)FlowCFL: generalized type-based reachability analysis: graph reduction and equivalence of CFL-based and type-based reachabilityProceedings of the ACM on Programming Languages10.1145/34282464:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428246
Mukherjee MKant PLiu ZRegehr J(2020)Dataflow-based pruning for speeding up superoptimizationProceedings of the ACM on Programming Languages10.1145/34282454:OOPSLA(1-24)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428245
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

View Options

Get Access

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