| // Copyright 2013 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package pointer |
| |
| // This file defines the main datatypes and Analyze function of the pointer analysis. |
| |
| import ( |
| "fmt" |
| "go/token" |
| "go/types" |
| "io" |
| "os" |
| "reflect" |
| "runtime" |
| "runtime/debug" |
| "sort" |
| |
| "golang.org/x/tools/go/callgraph" |
| "golang.org/x/tools/go/ssa" |
| "golang.org/x/tools/go/types/typeutil" |
| ) |
| |
| const ( |
| // optimization options; enable all when committing |
| optRenumber = true // enable renumbering optimization (makes logs hard to read) |
| optHVN = true // enable pointer equivalence via Hash-Value Numbering |
| |
| // debugging options; disable all when committing |
| debugHVN = false // enable assertions in HVN |
| debugHVNVerbose = false // enable extra HVN logging |
| debugHVNCrossCheck = false // run solver with/without HVN and compare (caveats below) |
| debugTimers = false // show running time of each phase |
| ) |
| |
| // object.flags bitmask values. |
| const ( |
| otTagged = 1 << iota // type-tagged object |
| otIndirect // type-tagged object with indirect payload |
| otFunction // function object |
| ) |
| |
| // An object represents a contiguous block of memory to which some |
| // (generalized) pointer may point. |
| // |
| // (Note: most variables called 'obj' are not *objects but nodeids |
| // such that a.nodes[obj].obj != nil.) |
| // |
| type object struct { |
| // flags is a bitset of the node type (ot*) flags defined above. |
| flags uint32 |
| |
| // Number of following nodes belonging to the same "object" |
| // allocation. Zero for all other nodes. |
| size uint32 |
| |
| // data describes this object; it has one of these types: |
| // |
| // ssa.Value for an object allocated by an SSA operation. |
| // types.Type for an rtype instance object or *rtype-tagged object. |
| // string for an instrinsic object, e.g. the array behind os.Args. |
| // nil for an object allocated by an instrinsic. |
| // (cgn provides the identity of the intrinsic.) |
| data interface{} |
| |
| // The call-graph node (=context) in which this object was allocated. |
| // May be nil for global objects: Global, Const, some Functions. |
| cgn *cgnode |
| } |
| |
| // nodeid denotes a node. |
| // It is an index within analysis.nodes. |
| // We use small integers, not *node pointers, for many reasons: |
| // - they are smaller on 64-bit systems. |
| // - sets of them can be represented compactly in bitvectors or BDDs. |
| // - order matters; a field offset can be computed by simple addition. |
| type nodeid uint32 |
| |
| // A node is an equivalence class of memory locations. |
| // Nodes may be pointers, pointed-to locations, neither, or both. |
| // |
| // Nodes that are pointed-to locations ("labels") have an enclosing |
| // object (see analysis.enclosingObject). |
| // |
| type node struct { |
| // If non-nil, this node is the start of an object |
| // (addressable memory location). |
| // The following obj.size nodes implicitly belong to the object; |
| // they locate their object by scanning back. |
| obj *object |
| |
| // The type of the field denoted by this node. Non-aggregate, |
| // unless this is an tagged.T node (i.e. the thing |
| // pointed to by an interface) in which case typ is that type. |
| typ types.Type |
| |
| // subelement indicates which directly embedded subelement of |
| // an object of aggregate type (struct, tuple, array) this is. |
| subelement *fieldInfo // e.g. ".a.b[*].c" |
| |
| // Solver state for the canonical node of this pointer- |
| // equivalence class. Each node is created with its own state |
| // but they become shared after HVN. |
| solve *solverState |
| } |
| |
| // An analysis instance holds the state of a single pointer analysis problem. |
| type analysis struct { |
| config *Config // the client's control/observer interface |
| prog *ssa.Program // the program being analyzed |
| log io.Writer // log stream; nil to disable |
| panicNode nodeid // sink for panic, source for recover |
| nodes []*node // indexed by nodeid |
| flattenMemo map[types.Type][]*fieldInfo // memoization of flatten() |
| trackTypes map[types.Type]bool // memoization of shouldTrack() |
| constraints []constraint // set of constraints |
| cgnodes []*cgnode // all cgnodes |
| genq []*cgnode // queue of functions to generate constraints for |
| intrinsics map[*ssa.Function]intrinsic // non-nil values are summaries for intrinsic fns |
| globalval map[ssa.Value]nodeid // node for each global ssa.Value |
| globalobj map[ssa.Value]nodeid // maps v to sole member of pts(v), if singleton |
| localval map[ssa.Value]nodeid // node for each local ssa.Value |
| localobj map[ssa.Value]nodeid // maps v to sole member of pts(v), if singleton |
| atFuncs map[*ssa.Function]bool // address-taken functions (for presolver) |
| mapValues []nodeid // values of makemap objects (indirect in HVN) |
| work nodeset // solver's worklist |
| result *Result // results of the analysis |
| track track // pointerlike types whose aliasing we track |
| deltaSpace []int // working space for iterating over PTS deltas |
| |
| // Reflection & intrinsics: |
| hasher typeutil.Hasher // cache of type hashes |
| reflectValueObj types.Object // type symbol for reflect.Value (if present) |
| reflectValueCall *ssa.Function // (reflect.Value).Call |
| reflectRtypeObj types.Object // *types.TypeName for reflect.rtype (if present) |
| reflectRtypePtr *types.Pointer // *reflect.rtype |
| reflectType *types.Named // reflect.Type |
| rtypes typeutil.Map // nodeid of canonical *rtype-tagged object for type T |
| reflectZeros typeutil.Map // nodeid of canonical T-tagged object for zero value |
| runtimeSetFinalizer *ssa.Function // runtime.SetFinalizer |
| } |
| |
| // enclosingObj returns the first node of the addressable memory |
| // object that encloses node id. Panic ensues if that node does not |
| // belong to any object. |
| func (a *analysis) enclosingObj(id nodeid) nodeid { |
| // Find previous node with obj != nil. |
| for i := id; i >= 0; i-- { |
| n := a.nodes[i] |
| if obj := n.obj; obj != nil { |
| if i+nodeid(obj.size) <= id { |
| break // out of bounds |
| } |
| return i |
| } |
| } |
| panic("node has no enclosing object") |
| } |
| |
| // labelFor returns the Label for node id. |
| // Panic ensues if that node is not addressable. |
| func (a *analysis) labelFor(id nodeid) *Label { |
| return &Label{ |
| obj: a.nodes[a.enclosingObj(id)].obj, |
| subelement: a.nodes[id].subelement, |
| } |
| } |
| |
| func (a *analysis) warnf(pos token.Pos, format string, args ...interface{}) { |
| msg := fmt.Sprintf(format, args...) |
| if a.log != nil { |
| fmt.Fprintf(a.log, "%s: warning: %s\n", a.prog.Fset.Position(pos), msg) |
| } |
| a.result.Warnings = append(a.result.Warnings, Warning{pos, msg}) |
| } |
| |
| // computeTrackBits sets a.track to the necessary 'track' bits for the pointer queries. |
| func (a *analysis) computeTrackBits() { |
| if len(a.config.extendedQueries) != 0 { |
| // TODO(dh): only track the types necessary for the query. |
| a.track = trackAll |
| return |
| } |
| var queryTypes []types.Type |
| for v := range a.config.Queries { |
| queryTypes = append(queryTypes, v.Type()) |
| } |
| for v := range a.config.IndirectQueries { |
| queryTypes = append(queryTypes, mustDeref(v.Type())) |
| } |
| for _, t := range queryTypes { |
| switch t.Underlying().(type) { |
| case *types.Chan: |
| a.track |= trackChan |
| case *types.Map: |
| a.track |= trackMap |
| case *types.Pointer: |
| a.track |= trackPtr |
| case *types.Slice: |
| a.track |= trackSlice |
| case *types.Interface: |
| a.track = trackAll |
| return |
| } |
| if rVObj := a.reflectValueObj; rVObj != nil && types.Identical(t, rVObj.Type()) { |
| a.track = trackAll |
| return |
| } |
| } |
| } |
| |
| // Analyze runs the pointer analysis with the scope and options |
| // specified by config, and returns the (synthetic) root of the callgraph. |
| // |
| // Pointer analysis of a transitively closed well-typed program should |
| // always succeed. An error can occur only due to an internal bug. |
| // |
| func Analyze(config *Config) (result *Result, err error) { |
| if config.Mains == nil { |
| return nil, fmt.Errorf("no main/test packages to analyze (check $GOROOT/$GOPATH)") |
| } |
| defer func() { |
| if p := recover(); p != nil { |
| err = fmt.Errorf("internal error in pointer analysis: %v (please report this bug)", p) |
| fmt.Fprintln(os.Stderr, "Internal panic in pointer analysis:") |
| debug.PrintStack() |
| } |
| }() |
| |
| a := &analysis{ |
| config: config, |
| log: config.Log, |
| prog: config.prog(), |
| globalval: make(map[ssa.Value]nodeid), |
| globalobj: make(map[ssa.Value]nodeid), |
| flattenMemo: make(map[types.Type][]*fieldInfo), |
| trackTypes: make(map[types.Type]bool), |
| atFuncs: make(map[*ssa.Function]bool), |
| hasher: typeutil.MakeHasher(), |
| intrinsics: make(map[*ssa.Function]intrinsic), |
| result: &Result{ |
| Queries: make(map[ssa.Value]Pointer), |
| IndirectQueries: make(map[ssa.Value]Pointer), |
| }, |
| deltaSpace: make([]int, 0, 100), |
| } |
| |
| if false { |
| a.log = os.Stderr // for debugging crashes; extremely verbose |
| } |
| |
| if a.log != nil { |
| fmt.Fprintln(a.log, "==== Starting analysis") |
| } |
| |
| // Pointer analysis requires a complete program for soundness. |
| // Check to prevent accidental misconfiguration. |
| for _, pkg := range a.prog.AllPackages() { |
| // (This only checks that the package scope is complete, |
| // not that func bodies exist, but it's a good signal.) |
| if !pkg.Pkg.Complete() { |
| return nil, fmt.Errorf(`pointer analysis requires a complete program yet package %q was incomplete`, pkg.Pkg.Path()) |
| } |
| } |
| |
| if reflect := a.prog.ImportedPackage("reflect"); reflect != nil { |
| rV := reflect.Pkg.Scope().Lookup("Value") |
| a.reflectValueObj = rV |
| a.reflectValueCall = a.prog.LookupMethod(rV.Type(), nil, "Call") |
| a.reflectType = reflect.Pkg.Scope().Lookup("Type").Type().(*types.Named) |
| a.reflectRtypeObj = reflect.Pkg.Scope().Lookup("rtype") |
| a.reflectRtypePtr = types.NewPointer(a.reflectRtypeObj.Type()) |
| |
| // Override flattening of reflect.Value, treating it like a basic type. |
| tReflectValue := a.reflectValueObj.Type() |
| a.flattenMemo[tReflectValue] = []*fieldInfo{{typ: tReflectValue}} |
| |
| // Override shouldTrack of reflect.Value and *reflect.rtype. |
| // Always track pointers of these types. |
| a.trackTypes[tReflectValue] = true |
| a.trackTypes[a.reflectRtypePtr] = true |
| |
| a.rtypes.SetHasher(a.hasher) |
| a.reflectZeros.SetHasher(a.hasher) |
| } |
| if runtime := a.prog.ImportedPackage("runtime"); runtime != nil { |
| a.runtimeSetFinalizer = runtime.Func("SetFinalizer") |
| } |
| a.computeTrackBits() |
| |
| a.generate() |
| a.showCounts() |
| |
| if optRenumber { |
| a.renumber() |
| } |
| |
| N := len(a.nodes) // excludes solver-created nodes |
| |
| if optHVN { |
| if debugHVNCrossCheck { |
| // Cross-check: run the solver once without |
| // optimization, once with, and compare the |
| // solutions. |
| savedConstraints := a.constraints |
| |
| a.solve() |
| a.dumpSolution("A.pts", N) |
| |
| // Restore. |
| a.constraints = savedConstraints |
| for _, n := range a.nodes { |
| n.solve = new(solverState) |
| } |
| a.nodes = a.nodes[:N] |
| |
| // rtypes is effectively part of the solver state. |
| a.rtypes = typeutil.Map{} |
| a.rtypes.SetHasher(a.hasher) |
| } |
| |
| a.hvn() |
| } |
| |
| if debugHVNCrossCheck { |
| runtime.GC() |
| runtime.GC() |
| } |
| |
| a.solve() |
| |
| // Compare solutions. |
| if optHVN && debugHVNCrossCheck { |
| a.dumpSolution("B.pts", N) |
| |
| if !diff("A.pts", "B.pts") { |
| return nil, fmt.Errorf("internal error: optimization changed solution") |
| } |
| } |
| |
| // Create callgraph.Nodes in deterministic order. |
| if cg := a.result.CallGraph; cg != nil { |
| for _, caller := range a.cgnodes { |
| cg.CreateNode(caller.fn) |
| } |
| } |
| |
| // Add dynamic edges to call graph. |
| var space [100]int |
| for _, caller := range a.cgnodes { |
| for _, site := range caller.sites { |
| for _, callee := range a.nodes[site.targets].solve.pts.AppendTo(space[:0]) { |
| a.callEdge(caller, site, nodeid(callee)) |
| } |
| } |
| } |
| |
| return a.result, nil |
| } |
| |
| // callEdge is called for each edge in the callgraph. |
| // calleeid is the callee's object node (has otFunction flag). |
| // |
| func (a *analysis) callEdge(caller *cgnode, site *callsite, calleeid nodeid) { |
| obj := a.nodes[calleeid].obj |
| if obj.flags&otFunction == 0 { |
| panic(fmt.Sprintf("callEdge %s -> n%d: not a function object", site, calleeid)) |
| } |
| callee := obj.cgn |
| |
| if cg := a.result.CallGraph; cg != nil { |
| // TODO(adonovan): opt: I would expect duplicate edges |
| // (to wrappers) to arise due to the elimination of |
| // context information, but I haven't observed any. |
| // Understand this better. |
| callgraph.AddEdge(cg.CreateNode(caller.fn), site.instr, cg.CreateNode(callee.fn)) |
| } |
| |
| if a.log != nil { |
| fmt.Fprintf(a.log, "\tcall edge %s -> %s\n", site, callee) |
| } |
| |
| // Warn about calls to non-intrinsic external functions. |
| // TODO(adonovan): de-dup these messages. |
| if fn := callee.fn; fn.Blocks == nil && a.findIntrinsic(fn) == nil { |
| a.warnf(site.pos(), "unsound call to unknown intrinsic: %s", fn) |
| a.warnf(fn.Pos(), " (declared here)") |
| } |
| } |
| |
| // dumpSolution writes the PTS solution to the specified file. |
| // |
| // It only dumps the nodes that existed before solving. The order in |
| // which solver-created nodes are created depends on pre-solver |
| // optimization, so we can't include them in the cross-check. |
| // |
| func (a *analysis) dumpSolution(filename string, N int) { |
| f, err := os.Create(filename) |
| if err != nil { |
| panic(err) |
| } |
| for id, n := range a.nodes[:N] { |
| if _, err := fmt.Fprintf(f, "pts(n%d) = {", id); err != nil { |
| panic(err) |
| } |
| var sep string |
| for _, l := range n.solve.pts.AppendTo(a.deltaSpace) { |
| if l >= N { |
| break |
| } |
| fmt.Fprintf(f, "%s%d", sep, l) |
| sep = " " |
| } |
| fmt.Fprintf(f, "} : %s\n", n.typ) |
| } |
| if err := f.Close(); err != nil { |
| panic(err) |
| } |
| } |
| |
| // showCounts logs the size of the constraint system. A typical |
| // optimized distribution is 65% copy, 13% load, 11% addr, 5% |
| // offsetAddr, 4% store, 2% others. |
| // |
| func (a *analysis) showCounts() { |
| if a.log != nil { |
| counts := make(map[reflect.Type]int) |
| for _, c := range a.constraints { |
| counts[reflect.TypeOf(c)]++ |
| } |
| fmt.Fprintf(a.log, "# constraints:\t%d\n", len(a.constraints)) |
| var lines []string |
| for t, n := range counts { |
| line := fmt.Sprintf("%7d (%2d%%)\t%s", n, 100*n/len(a.constraints), t) |
| lines = append(lines, line) |
| } |
| sort.Sort(sort.Reverse(sort.StringSlice(lines))) |
| for _, line := range lines { |
| fmt.Fprintf(a.log, "\t%s\n", line) |
| } |
| |
| fmt.Fprintf(a.log, "# nodes:\t%d\n", len(a.nodes)) |
| |
| // Show number of pointer equivalence classes. |
| m := make(map[*solverState]bool) |
| for _, n := range a.nodes { |
| m[n.solve] = true |
| } |
| fmt.Fprintf(a.log, "# ptsets:\t%d\n", len(m)) |
| } |
| } |
