Free-Me: A Static Analysis for Automatic Individual Object ReclamationMotivationExampleExplicit Reclamation as the solutionFreeMe as the solutionOutlineFreeMe AnalysisPointer AnalysisPointer Analysis in more depth (1) Data StructuresPointer Analysis in more depth (2) Calculating the Points-To relationInterprocedural componentGenerating summaries in more depthThe need for liveness analysisAdding LivenessLiveness AnalysisWhere can we free it?Free placement issuesLimitations & ExtensionsRuntime support for FreeMeExperimental EvaluationVolume freed – in MBSlide 22Comparing FreeMe & other approachesMark/sweep – timeMark/sweep – GC timeGenMS – timeGenMS – GC timeBloat – GC timeConclusionsDiscussionFree-Me: A Static Analysis for Automatic Individual Object Reclamation Samuel Z. Guyer, Kathryn McKinley, Daniel FramptonPresented by: Dimitris PrountzosSome slides adapted from the original PLDI talkMotivationAutomatic memory reclamation (GC)No need for explicit “free”Garbage collector reclaims memoryEliminates many programming errorsProblem: when do we get memory back?Frequent GCs: Reclaim memory quickly (minimize memory footprint), with high overheadInfrequent GCs: Lower overhead, but lots of garbage in memoryCan we combine the software engineering advantage of garbage collection with the low-cost incremental reclamation of explicit memory management ?Can we combine the software engineering advantage of garbage collection with the low-cost incremental reclamation of explicit memory management ?ExampleNotice: String idName is often garbageMemory:void parse(InputStream stream) { while (not_done) { String idName = stream.readToken(); Identifier id = symbolTable.lookup(idName); if (id == null) { id = new Identifier(idName); symbolTable.add(idName, id); } computeOn(id);}}Read a token (new String)Look up insymbol tableIf not there, create new identifier, add to symbol tableCompute onidentifierExplicit Reclamation as the solutionGarbage does not accumulateMemory:void parse(InputStream stream) { while (not_done) { String idName = stream.readToken(); Identifier id = symbolTable.lookup(idName) if (id == null) { id = new Identifier(idName); symbolTable.add(idName, id); } else free(idName); computeOn(id);}}String idName is garbage, free immediatelyFreeMe as the solutionAdds free() automaticallyFreeMe compiler pass inserts calls to free()Preserve software engineering benefitsCan’t determine lifetimes for all objectsWorks with the garbage collectorImplementation of free() depends on collectorGoal:Incremental, “eager” memory reclamation Results: reduce GC load, improve performancePotential: 1.7X performancemalloc/free vs GCin tight heaps(Hertz & Berger, OOPSLA 2005)Outline•Motivation•Analysis•Runtime support•Experimental evaluation•ConclusionsFreeMe AnalysisGoal:Determine when an object becomes unreachable Not a whole-program analysis*Idea: pointer analysis + livenessPointer analysis for reachabilityLiveness analysis for whenWithin a method, for allocation site “p = new A” where can we place a call to “free(p)”?I’ll describe the interprocedural parts laterPointer AnalysisidNamesymbolTablereadTokenStringIdentifier(global)idString idName = stream.readToken();Identifier id = symbolTable.lookup(idName);if (id == null) { id = new Identifier(idName); symbolTable.add(idName, id);}computeOn(id);Connectivity graphVariablesAllocation sitesGlobals (statics)Analysis algorithm Flow-insensitive, field-insensitivePointer Analysis in more depth (1) Data Structuresvoid function(A p1, A p2, A p3){ v1 = new O p1.f = v1 p2 = p1.f p3 = p1 }Pointer Analysis in more depth (2)Calculating the Points-To relation p1p1Np1Np1NI1NI1p2p2Np2Np2NI2NI2p3p3Np3Np3NI3NI3€ ∀i,PtsTo( pi) = {NPi}∀i,PtsTo(NPi) = {NIi}∀i,PtsTo(NIi) = {NIi}v1v1O1O1€ ∀n ∈ PtsTo( p1) : PtsTo(n)∪ = PtsTo(v1)€ PtsTo( p2)∪ = PtsTo * ( p1)€ PtsTo( p3)∪ = PtsTo( p1)€ PtsTo( p1) = {NP1,O1}PtsTo( p2) = {NP1,O1,NI1,NP 2}PtsTo( p3) = {NP1,NP3}Interprocedural componentDetection of factory methodsReturn value is a new objectCan be freed by the callerEffects of methods calledDescribes how parameters are connectedCompilation strategy:Summaries pre-computed for all methodsFree-me only applied to hot methodsString idName = stream.readToken();symbolTable.add(idName, id);Hashtable.add: (0 → 1) (0 → 2)Generating summaries in more depth€ PtsTo( p1) = {NP1,O1}PtsTo( p2) = {NP1,O1,NI1,NP 2}PtsTo( p3) = {NP1,NP3}€ ( p2, p1),( p2,*p1)( p3, p1)p1p1Np1Np1NI1NI1p2p2Np2Np2NI2NI2p3p3Np3Np3NI3NI3v1v1O1O1void function(A p1, A p2, A p3){ v1 = new O p1.f = v1 p2 = p1.f p3 = p1 }Getield is needed because a single pointer link in summary may represent multiple pointers in the calleeGetield is needed because a single pointer link in summary may represent multiple pointers in the calleeThe need for liveness analysis•Liveness identifies when objects become unreachable, not just whether or not they escape idNamesymbolTablereadTokenStringIdentifier(global)idAdding LivenessKey :idNamereadTokenStringIdentifier(global)An object is reachable only when all incoming pointers are live From a variable: Live range of the variable From a global: Live from the pointer store onward Live from the pointer store until source object becomes unreachableFrom other object:Reachability is union of all these live rangesLiveness AnalysisComputed as sets of edgesVariablesHeappointersString idName = stream.readToken();id = new Identifier(idName);computeOn(id);if (id == null)Identifier id = symbolTable.lookup(idName);symbolTable.add(idName, id);idName(global)readTokenStringIdentifierWhere can we free it?Where object exists -minus-Where reachableString idName = stream.readToken();id = new Identifier(idName);computeOn(id);if (id == null)Identifier id = symbolTable.lookup(idName);symbolTable.add(idName, id);readTokenStringCompiler inserts call to free(idName)Free placement issues•Select earliest point A, eliminate all B: A dom B•Deal with double free’sLimitations & Extensions•Free-me frees short-lived objects with explicit pointers to them in the code•Factory variability•Potential extensions:–Container internals•interprocedural liveness & pointer analysis || shape analysis–Large data structures•Global context sensitive heap model
View Full Document
Unlocking...