Slide 1Memory BugsMemory Leaks in Managed LanguagesRelated WorkCork1. Calculating Type Points-To2. Differencing GraphsFinding Growth (RRT)Reported CandidatesFinding Data StructureImplementation and MethodologyEfficiency and ScalabilitySpace OverheadTime OverheadTime OverheadDynamic Heap Analysis with CorkEclipse 115789Eclipse 115789: CPFGEclipse 115789: SliceEclipse 115789Eclipse 115789: SliceEclipse 115789Cork’s ContributionsWhat else can the GC tell us?Department of Computer SciencesCork: Dynamic Memory Leak Detection with Garbage CollectionMaria JumpKathryn S. McKinley{mjump,mckinley}@cs.utexas.eduDepartment of Computer SciencesMemory BugsWhat memory bugs do explicitly managed languages have?Does managed memory solve all our memory problems?Department of Computer SciencesMemory Leaks in Managed LanguagesResult from inadvertently maintaining references to “dead” objectsBest case: increases GC workloadWorst case: causes program crashDynamically analyze heap to detect systematic heap growthDepartment of Computer Sciences4Related WorkOffline Techniques:Static analysis [Heine et al. 03]Heap differencing [JProbe, DePauw et al. 98, 99, 00]Allocation and/or usage tracking [OptimizeIt, Rationale, Purify, HAT, HPROF, Shaham et al. 00]Online Techniques:Leakbot (partially online) [Mitchell et al. 03]Adaptive usage tracking [Chilimbi et al. 04, Bond et al. 06]Cork accurately pinpoints systematicheap growth completely onlineDepartment of Computer SciencesCorkOpportunity: tracing GC visits all the object in the heap!Build heap summarization graphClass points-from graph (CPFG)Summarizes volume of nodes and edgesIdentify growth by differencing CPFGs across collectionsIdentify candidates using node rankIdentify the data structure using edge rankDepartment of Computer Sciences31. Calculating Type Points-ToHeap342214111Type Points-To (TPT) =instance =typeDepartment of Computer Sciences122. Differencing Graphs12122321TPTi+1TPTi+21411212334TPTi1Cork’s optimizations:Keeps 3 graphsPrunes obviously non-growing partsVolume decay guards against premature pruningRanks nodes/edges11111111Department of Computer Sciences141141114Find nodes of types t that grow Vt(i) > (1 -f) * Vt(i-1)i is the phase & f is a decay factor e.g., .05Rank nodes and edgesri = ri-1 +/- pi * (Q - 1)P add to rank if type grows in phase p, subtract if it shrinksQ is a ratio > 1 of Vi to Vi-1 Designate node as a candidate if rt(i) > RthresholdFinding Growth (RRT)Department of Computer SciencesReported Candidates# of CandidatesSRTRRTjessSPECjbbfopDepartment of Computer SciencesFinding Data StructureType is not enoughGrowing edges identify the data structureRank edges Calculate a slice from each candidateSet of all paths (n0…nn) such that“Sees” beyond non-candidate nodes111114141401 kknnrDepartment of Computer SciencesImplementation and MethodologyJikes RVM with MMTkBenchmarks:SPECjvm98, DaCapo, SPECjbb2000Eclipse 3.1.2Garbage collectorGenerational with 4MB bounded nurseryFor performance, report application onlyReplay compilation2nd run methodologyDepartment of Computer SciencesEfficiency and ScalabilityNode/type data stored in type information block (TIB) adding 5 words1 word for type volume and edge list pointer for each of the previous 4 collections1 word for # of phases (p)Edge data stored in listsPrune parts of TPFG that are non-growingAre there ways to implement the type summary graph?Department of Computer SciencesSpace Overheadjess EclipseGeomean# of typesbm+VM 1744 3365 1747TPFG avg 318 667 334TPFG max 319 775 346# of edgesTPFG avg 844 4090 904TPFG max 861 7585 1142% pruned 66% 42% 60%Increased Alloc % 0.094% 0.167% 0.233%19%2.7X0.233%Department of Computer SciencesUMCPTime OverheadNormalized Total TimeHeap Size Relative to MinimumDepartment of Computer SciencesTime OverheadIs this good enough?Would you add it to your system?Department of Computer SciencesDynamic Heap Analysis with CorkCork identified:Systematic heap growthGrowing classesGrowing data structureBenchmarks:fop – application designjess – in inputSPECjbb2000 – memory leakEclipse 3.1.2 #115789 – repeatedly performing a structural (recursive) dif leaks memory012345compressjessraytracedbjavacmpegaudiomtrtjackpseudojbbSPECjbbantlrbloatfopjythonpmdpsxalanSPECjbbfopjessDepartment of Computer SciencesEclipse 115789Heap Occupancy (MB)Time (MB of allocation)Department of Computer SciencesEclipse 115789: CPFG3365 classes loaded (1773 in Eclipse)Average graph:667 nodes4090 edgesDepartment of Computer SciencesEclipse 115789: SliceString[]Object[]ArrayListResourceCompareInput$FilteredBufferedResourceNodeFolderFilePathIdentifies 7 candidates: rt > rthresCalculates slice from each candidate: set of all paths (n0…nn) s.t. rn(k+1)n(k)<0 ResourceCompareInputDepartment of Computer SciencesEclipse 115789Heap Occupancy (MB)Time (MB of allocation)Department of Computer SciencesEclipse 115789: SliceString[]Object[]ArrayListResourceCompareInput$FilteredBufferedResourceNodeFolderFilePathIdentifies 7 candidates: rt > rthresCalculates slice from each candidate: set of all paths (n0…nn) s.t. rn(k+1)n(k)<0 ResourceCompareInputHashMapDepartment of Computer SciencesEclipse 115789Heap Occupancy (MB)Time (MB of allocation)Department of Computer SciencesCork’s ContributionsPerforms dynamic heap analysis to detect systematic heap growthUses a class points-from graph to summarize volume relations<0.5% space overhead~2% time overheadAccurately identifiesUser-defined classes causing the growthData structure containing the growthDepartment of Computer SciencesWhat else can the GC tell us?Testing time?In
View Full Document