« Back to blog

Review on "Cork: Dynamic Memory Leak Detection for Garbage-Collected Languages"

Another one of my reviews which was my assignment. This is the original paper: http://dl.acm.org/citation.cfm?id=1190224

Cork is a memory leak detecting tool that looks into the detection of leaks created by useless objects in managed programming languages such as Java and C#. The idea here is not to pinpoint the site of the memory leak which like in the case of Sleigh1 was a source code line. Instead Cork looks to identify the Data Structure responsible for growth of the heap and thus the cause of a memory leak.

Cork does this by summarizing the live objects or types in the heap. This is done by piggybacking the Garbage-collector which essentially begins the process of garbage collection by scanning for all the live objects starting from the roots. This piggy backing is done using the type information block or any such analogous entity which is usually required for the implementation of managed programming languages. The TIBs, provide a rich source of type information for objects which are required by the compiler for proper functioning. During the scanning phase, a Type Points-From Graph (TPFG) is created in which, the nodes are the different Types in the heaps. The type nodes are annotated with the volume or number of objects in the heap of that particular type. The edges between the type nodes are Points-From edges, i.e. when an edge is drawn from t2 to t1, it means that objects of type t2 are pointed or referenced from objects of type t1. The edge itself is annotated with a weight which denotes the number of objects of type t2 referenced by type t1.

Such a TPFG is created while the scanning process itself. Each time an object is encountered the corresponding nodes and required edges are updated. This induces a very low time overhead which makes this process an ideal candidate for production environments. When multiple such TPFGs are collected, differences are calculated between them and trends of growths are observed. To be sure of the non-decreasing nature of the growth, a ranking scheme for the node types is used. A ranking threshold is used which is used to display all candidate types which rank higher than the threshold. The ranking scheme used and described by the paper is the Ratio Ranking Technique, which uses the ratios between volumes of tow consecutive TPFGs. Furthermore, the phenomena of jitter or fluctuating volume patterns is accounted for using a decay factor. The idea is to account for types which show an over all growth pattern despite fluctuating volumes.

Thereafter, a slice is constructed through the TPFG. By starting at the candidate type node, all the growing edges are traced until a non growing type node is encountered with non growing type edges. This is also accompanied with a Site Map for all the candidate types which essentially shows the allocation sites in the code base, which can be a combination of method name and source code line number or byte code offset. The slice along with the site map give a clear picture of the potential memory leaks along with their exact location in code.

The evaluation for this technique look good and quite accurate. However, 0only specific examples have been shown. It might have made a sound argument to show an extensive study on a range of candidate programs or at least on a range of candidate memory leak bugs. Nonetheless, the examples shown in the evaluations are compelling, especially due to the low memory and performance overheads. However, this evaluation has not shown one simple situation that comes to mind: what if the candidate program required to have a growing heap size. While such a situation might be rare the paper has failed to show if something like that will give a false positive or not. In other words, what if the requirements were for a growing heap size, where all the objects in the heap would be used. It is important to note that this technique relies on the premise that a growing type/object size necessarily imply a memory leak. Which may not always be true. And this is the source of my question regarding this paper: How can you be sure that a growing heap size is definitely an indicator of an increase in unused objects which are being referenced? In other words, how does this technique ensure/verify that the objects responsible for the growing heap size are indeed not going to be used anymore? Because, unlike the Bell1 technique, there is no mechanism in place to indicate the staleness of the objects.

1. Michael D. Bond and Kathryn S. McKinley. 2006. Bell: bit-encoding online memory leak detection. InProceedings of the 12th international conference on Architectural support for programming languages and operating systems (ASPLOS-XII). ACM, New York, NY, USA, 61-72. DOI=10.1145/1168857.1168866 http://doi.acm.org/10.1145/1168857.1168866