Utilizing object reference graphs and garbage collection roots to detect memory leaks in offline memory monitoring

ABSTRACT

Complex software systems often suffer from performance problems caused by memory anomalies such as memory leaks. While the proliferation of objects is rather easy to detect using state-of-the-art memory monitoring tools, extracting a leak's root cause, i.e., identifying the objects that keep the accumulating objects alive, is still poorly supported. Most state-of-the-art tools rely on the dominator tree of the object graph and thus only support single-object ownership analysis. Multi-object ownership analysis, e.g., when the leaking objects are contained in multiple collections, is not possible by merely relying on the dominator tree. We present an efficient approach to continuously collect GC root information (e.g., static fields or thread-local variables) in a trace-based memory monitoring tool, as well as algorithms that use this information to calculate the transitive closure (i.e., all reachable objects) and the GC closure (i.e., objects that are kept alive) for arbitrary heap object groups. These closures allow to derive various metrics for heap object groups that can be used to guide the user during memory leak analysis. We implemented our approach in AntTracks, an offline memory monitoring tool, and demonstrate its usefulness by comparing it with other widely used tools for memory leak detection such as the Eclipse Memory Analyzer. Our evaluation shows that collecting GC root information tracing introduces about 1% overhead, in terms of run time as well as trace file size.

References

1. Edward E. Aftandilian, Sean Kelley, Connor Gramazio, Nathan Ricci, Sara L. Su, and Samuel Z. Guyer. 2010. Heapviz: Interactive Heap Visualization for Program Understanding and Debugging. In Proceedings of the 5th International Symposium on Software Visualization (SOFTVIS '10). ACM, New York, NY, USA, 53--62.
2. Stephen Alstrup and Peter W. Lauridsen. 1996. A Simple Dynamic Algorithm for Maintaining a Dominator Tree. Technical Report.
3. Earl T Barr, Christian Bird, and Mark Marron. 2013. Collecting a heap of shapes. In Proceedings of the 2013 International Symposium on Software Testing and Analysis. ACM, 123--133.
4. Verena Bitto, Philipp Lengauer, and Hanspeter Mössenböck. 2015. Efficient Rebuilding of Large Java Heaps from Event Traces. In Proc. of the Principles and Practices of Programming on The Java Platform (PPPJ '15). 76--89.
5. Stephen M Blackburn, Robin Garner, Chris Hoffmann, Asjad M Khang, Kathryn S McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z Guyer, et al. 2006. The DaCapo benchmarks: Java benchmarking development and analysis. In ACM Sigplan Notices, Vol. 41. ACM, 169--190.
6. Adriana E Chis, Nick Mitchell, Edith Schonberg, Gary Sevitsky, Patrick O'Sullivan, Trevor Parsons, and John Murphy. 2011. Patterns of memory inefficiency. In European Conference on Object-Oriented Programming. Springer, 383--407.
7. Keith D Cooper, Timothy J Harvey, and Ken Kennedy. 2001. A simple, fast dominance algorithm. Software Practice & Experience 4, 1--10 (2001), 1--8.
8. Diego Costa, Artur Andrzejak, Janos Seboek, and David Lo. {n. d.}. Empirical Study of Usage and Performance of Java Collections. ({n. d.}).
9. Diego Costa and Rivalino Matias Jr. 2015. Characterization of Dynamic Memory Allocations in Real-World Applications: An Experimental Study. In 2015 IEEE 23rd International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems. IEEE, 93--101.
10. R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. 1989. An Efficient Method of Computing Static Single Assignment Form. In Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '89). ACM, New York, NY, USA, 25--35.
11. Wim De Pauw, Erik Jensen, Nick Mitchell, GarySevitsky, John Vlissides, and Jeaha Yang. 2002. Visualizing the execution of Java programs. In Software Visualization. Springer, 151--162.
12. Wim De Pauw and Gary Sevitsky. 1999. Visualizing Reference Patterns for Solving Memory Leaks in Java. In ECOOP' 99 --- Object-Oriented Programming, Rachid Guerraoui (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 116--134.
13. J. Eve and R Kurki-Suonio. 1977. On computing the transitive closure of a relation. Acta Informatica 8, 4 (oct 1977), 303--314.
14. R. Falke, R. Klein, R. Koschke, and J. Quante. 2005. The Dominance Tree in Visualizing Software Dependencies. In 3rd IEEE International Workshop on Visualizing Software for Understanding and Analysis. 1--6.
15. Eclipse Foundation. 2018. Eclipse Memory Analyzer (MAT) (last accessed May 11, 2018). https://www.eclipse.org/mat/. (2018).
16. Mohammadreza Ghanavati, Diego Costa, Artur Andrzejak, and Janos Seboek. 2018. Memory and Resource Leak Defects in Java Projects: An Empirical Study. In Proceedings of the 40th International Conference on Software Engineering: Companion Proceeedings (ICSE '18). ACM, New York, NY, USA, 410--411.
17. T. Hill, J. Noble, and J. Potter. 2000. Scalable visualisations with ownership trees. In Proceedings 37th International Conference on Technology of Object-Oriented Languages and Systems. TOOLS-Pacific 2000. 202--213.
18. Trent Hill, James Noble, and John Potter. 2002. Scalable visualizations of object-oriented systems with ownership trees. Journal of Visual Languages & Computing 13, 3 (2002), 319--339.
19. Maria Jump and Kathryn S. McKinley. 2007. 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). ACM, New York, NY, USA, 31--38.
20. Donald E. Knuth. 1971. Top-down syntax analysis. Acta Informatica 1, 2 (01 Jun 1971), 79--110.
21. Philipp Lengauer, Verena Bitto, Stefan Fitzek, Markus Weninger, and Hanspeter Mössenböck. 2016. Efficient Memory Traces with Full Pointer Information. In Proc. of the 13th Int'l. Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools (PPPJ '16).
22. Philipp Lengauer, Verena Bitto, and Hanspeter Mössenböck. 2015. Accurate and Efficient Object Tracing for Java Applications. In Proc. of the 6th ACM/SPEC Int'l. Conference on Performance Engineering (ICPE '15). 51--62.
23. Philipp Lengauer, Verena Bitto, and Hanspeter Mössenböck. 2016. Efficient and Viable Handling of Large Object Traces. In Proc. of the 7th ACM/SPEC on Int'l. Conference on Performance Engineering (ICPE '16). 249--260.
24. Philipp Lengauer, Verena Bitto, Hanspeter Mössenböck, and Markus Weninger. 2017. A Comprehensive Java Benchmark Study on Memory and Garbage Collection Behavior of DaCapo, DaCapo Scala, and SPECjvm2008. In Proceedings of the 8th ACM/SPEC on International Conference on Performance Engineering (ICPE '17). ACM, New York, NY, USA, 3--14.
25. Thomas Lengauer and Robert Endre Tarjan. 1979. A Fast Algorithm for Finding Dominators in a Flowgraph. ACM Trans. Program. Lang. Syst. 1, 1 (Jan. 1979), 121--141.
26. M. Marron, C. Sanchez, Z. Su, and M. Fahndrich. 2013. Abstracting runtime heaps for program understanding. IEEE Transactions on Software Engineering 39, 6 (June 2013), 774--786.
27. Nick Mitchell. 2006. The Runtime Structure of Object Ownership. In Proceedings of the 20th European Conference on Object-Oriented Programming (ECOOP '06). Springer-Verlag, Berlin, Heidelberg, 74--98.
28. Nick Mitchell, Edith Schonberg, and Gary Sevitsky. 2009. Making Sense of Large Heaps. In Proceedings of the 23rd European Conference on ECOOP 2009 --- Object-Oriented Programming (Genoa). Springer-Verlag, Berlin, Heidelberg, 77--97.
29. Nick Mitchell and Gary Sevitsky. 2007. The Causes of Bloat, the Limits of Health. In Proceedings of the 22Nd Annual ACM SIGPLAN Conference on Object-oriented Programming Systems and Applications (OOPSLA '07). ACM, New York, NY, USA, 245--260.
30. Oracle. 2018. The HotSpot Group (last accessed May 11, 2018). http://openjdk.java.net/groups/hotspot/. (2018).
31. Oracle. 2018. Netbeans Profiler (last accessed May 11, 2018). https://profiler.netbeans.org/. (2018).
32. Oracle. 2018. VisualVM: All-in-One Java Troubleshooting Tool (last accessed May 11, 2018). https://visualvm.github.io/. (2018).
33. G. Ramalingam and Thomas Reps. 1994. An Incremental Algorithm for Maintaining the Dominator Tree of a Reducible Flowgraph. In Proceedings of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '94). ACM, New York, NY, USA, 287--296.
34. Derek Rayside and Lucy Mendel. 2007. Object Ownership Profiling: A Technique for Finding and Fixing Memory Leaks. In Proceedings of the Twenty-second IEEE/ACM International Conference on Automated Software Engineering (ASE '07). ACM, New York, NY, USA, 194--203.
35. Derek Rayside, Lucy Mendel, and Daniel Jackson. 2006. A Dynamic Analysis for Revealing Object Ownership and Sharing. In Proceedings of the 2006 International Workshop on Dynamic Systems Analysis (WODA '06). ACM, New York, NY, USA, 57--64.
36. Steven P Reiss. 2009. Visualizing the Java heap - Demonstration Proposal. In Software Maintenance, 2009. ICSM 2009. IEEE International Conference on. IEEE, 389--390.
37. S. P. Reiss. 2009. Visualizing the Java heap to detect memory problems. In 2009 5th IEEE International Workshop on Visualizing Software for Understanding and Analysis. 73--80.
38. Steven P. Reiss. 2010. Visualizing the Java Heap. In Proceedings of the 32Nd ACM/IEEE International Conference on Software Engineering - Volume 2 (ICSE '10). ACM, New York, NY, USA, 251--254.
39. Nathan P. Ricci, Samuel Z. Guyer, and J. Eliot B. Moss. 2013. Elephant Tracks: Portable Production of Complete and Precise Gc Traces. In Proceedings of the 2013 International Symposium on Memory Management (ISMM '13). ACM, New York, NY, USA, 109--118.
40. C. Ruggieri and T. P. Murtagh. 1988. Lifetime Analysis of Dynamically Allocated Objects. In Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '88). ACM, New York, NY, USA, 285--293.
41. Robert Tarjan. 1971. Depth-first search and linear graph algorithms. In 12th Annual Symposium on Switching and Automata Theory (swat 1971). IEEE, 114--121.
42. Markus Weninger, Philipp Lengauer, and Hanspeter Mössenböck. 2017. User-centered Offline Analysis of Memory Monitoring Data. In Proc. of the 8th ACM/SPEC on Int'l. Conference on Performance Engineering (ICPE '17). 357--360.
43. Markus Weninger and Hanspeter Mössenböck. 2018. User-defined Classification and Multi-level Grouping of Objects in Memory Monitoring. In Proceedings of the 9th ACM/SPEC International Conference on Performance Engineering (ICPE 2018) (ICPE 2018).

Index Terms

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Clustering and classification

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

  • Software notations and tools

    • Software maintenance tools

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis