+++ /dev/null
-// 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))
- }
-}
projects / dotfiles / .git / blobdiff