Documentation
¶
Overview ¶
Package escape provides an escape analysis which computes a representation of which references in the program are to objects that are local to the current function and goroutine. This information can be used to recover local reasoning even in the face of concurrent goroutine execution. This implementation is inspired by:
John Whaley and Martin Rinard. 1999. Compositional Pointer And Escape Analysis For Java Programs. SIGPLAN Not. 34, 10 (Oct. 1999), 187–206.
Index ¶
- Constants
- func AddressOfType(t types.Type) types.Type
- func AsImplInterfaceType(a types.Type) types.Type
- func CanPointTo(a, b types.Type) bool
- func ChannelContentsType(t types.Type) types.Type
- func CompatibleTypes(tpA, tpB types.Type) (r bool)
- func InitializeEscapeAnalysisState(state *dataflow.State) error
- func IsAbstractType(tp types.Type) (r bool)
- func IsEscapeTracked(t types.Type) bool
- func NillableDerefType(t types.Type) types.Type
- func TypecheckEscapeGraph(g *EscapeGraph) error
- type Edge
- type EscapeGraph
- func (g *EscapeGraph) AddEdge(src *Node, dest *Node, newFlag edgeFlags) (changed bool)
- func (g *EscapeGraph) AddNode(n *Node) (changed bool)
- func (g *EscapeGraph) AnalogousSubnode(base *Node, subnode *Node) *Node
- func (g *EscapeGraph) Call(pre *EscapeGraph, receiver *Node, args []*Node, freeVars []*Node, rets []*Node, ...)
- func (g *EscapeGraph) CallUnknown(args []*Node, rets []*Node, funcName string)
- func (g *EscapeGraph) Clone() *EscapeGraph
- func (g *EscapeGraph) CloneReachable(roots []*Node) *EscapeGraph
- func (g *EscapeGraph) Edges(src, dest *Node, mask edgeFlags) []*Edge
- func (g *EscapeGraph) EnsureLoadNode(loadOp any, tp types.Type, base *Node) *Node
- func (g *EscapeGraph) FieldSubnode(base *Node, field string, tp types.Type) *Node
- func (g *EscapeGraph) Graphviz() string
- func (g *EscapeGraph) ImplementationSubnode(base *Node, concreteTp types.Type) *Node
- func (g *EscapeGraph) IsSubnode(n *Node) bool
- func (g *EscapeGraph) IsSubnodeEdge(base, n *Node) bool
- func (g *EscapeGraph) LessEqual(h *EscapeGraph) (isLessEq bool, reason string)
- func (g *EscapeGraph) LoadField(valNode *Node, addrNode *Node, loadOp any, field string, tp types.Type)
- func (g *EscapeGraph) Matches(h *EscapeGraph) bool
- func (g *EscapeGraph) Merge(h *EscapeGraph)
- func (g *EscapeGraph) MergeNodeStatus(n *Node, s EscapeStatus, rationale *dataflow.EscapeRationale)
- func (g *EscapeGraph) Pointees(src *Node) map[*Node]struct{}
- func (g *EscapeGraph) StoreField(addrNode, valNode *Node, field string, tp types.Type)
- func (g *EscapeGraph) WeakAssign(dest *Node, src *Node)
- type EscapeStatus
- type FunctionImplType
- type ImplType
- type Node
- type NodeGroup
- func (g *NodeGroup) AddForeignNode(n *Node) (changed bool)
- func (g *NodeGroup) AllocNode(instr ssa.Instruction, t types.Type) *Node
- func (g *NodeGroup) IndexedAllocNode(instr ssa.Instruction, index string, t types.Type) *Node
- func (g *NodeGroup) LoadNode(location any, instr ssa.Instruction, t types.Type) *Node
- func (g *NodeGroup) NewNode(kind nodeKind, debug string, tp types.Type) *Node
- func (g *NodeGroup) NilNode() *Node
- func (g *NodeGroup) ParamNode(param ssa.Value) *Node
- func (g *NodeGroup) ReturnNode(i int, t types.Type) *Node
- func (g *NodeGroup) UnknownReturnNode(funcName string) *Node
- func (g *NodeGroup) UnusedNode() *Node
- func (g *NodeGroup) ValueNode(variable ssa.Value) *Node
- type ProgramAnalysisState
Constants ¶
const ( // KindAlloc cells of allocations that happen locally KindAlloc nodeKind = iota // KindParam Pointees of initial pointer-like parameters KindParam // KindLoad Represent the object loaded from a pointer/field of an external object KindLoad // KindGlobal The memory location of a global/package level variable (pointee of ssa.Global) KindGlobal // KindGlobalVar Pointer to the location of a heap object (represents the ssa.Global itself) KindGlobalVar // KindVar A local variable, i.e. SSA var KindVar // KindParamVar A parameter variable (both formals and free variables/method receiver) KindParamVar // KindReturn The return value of the current function KindReturn // KindUnknown A return value from an unanalyzed method without a summary KindUnknown )
const ( // EdgeInternal flags internal edges EdgeInternal edgeFlags = 1 << iota // EdgeExternal flags external edges EdgeExternal // EdgeSubnode flags subnodes EdgeSubnode // EdgeAll is the conjunction of all types of edges EdgeAll = EdgeInternal | EdgeExternal | EdgeSubnode )
Variables ¶
This section is empty.
Functions ¶
func AddressOfType ¶
AddressOfType computes what type would point to a given type. It is roughly the inverse of NillableDerefType.
func AsImplInterfaceType ¶
AsImplInterfaceType returns the corresponding interface type, if the input is is an abstract interface implementation type, otherwise it returns nil.
func CanPointTo ¶
CanPointTo determines whether a escape graph node labeled with type a can have a type-correct outedge to a node with type b. The result is conservative in the sense that it defaults to true in the cases where the type system doesn't give enough information, or the types don't yet have a typechecking rule.
func ChannelContentsType ¶
ChannelContentsType gives the type of the contents of a channel. No-op otherwise
func CompatibleTypes ¶
CompatibleTypes returns true if a node of tpA can represent a node of tpB. Conservatively return true if either doesn't have a type (represented by tpA or tpB being nil). Represent here means that tpA is tpB or tpA satisfies the interface tpB.
func InitializeEscapeAnalysisState ¶
InitializeEscapeAnalysisState initializes the escape analysis' state inside the dataflow state Returns an error if an error is encountered during the escape analysis.
func IsAbstractType ¶
IsAbstractType returns true if the input is an abstract type, i.e. an interface impl or a function impl with no specific function.
func IsEscapeTracked ¶
IsEscapeTracked returns true if t is a type that must be tracked by the escape analysis, because it is either a pointer-like type ("nillables"), or it is a struct that may directly contain pointer-like types. Struct types are usually represented by pointers to a memory object containing the struct, except when the struct is directly an argument or return value from a function.
func NillableDerefType ¶
NillableDerefType gives the type of the result of dereferencing nilable (pointer-like) types. No-op (returns the argument) for all other types. The standard Go type system cannot represent the type of some nilable types, such as maps or channels. A map type is effectively a pointer to the actual map implementation object, but this implementation cannot be manipulated directly in Go, so has no type. This is unlike, e.g. *struct{} and struct{}, where the dereference type struct{} is a first-class value. The table is:
nilable deref
------- -----
T* T
[]T [-1]T
func() impl func()
map impl map
chan impl chan
interface{} impl interface
Slices are isomorphic to a struct value with three fields: a pointer to an array, and integer length/capacity. The deref is therefore an array of the same type, but because the size may be dynamic, we use -1 as the size (this matches the ssa package convention). Note that []int is a slice, and [-1]int is an array, with the former pointing to the later! The deref of these "opaque" types is formed by wrapping them in a `impl`, to make a pseudo-type. This is currently not supported, and these types are passed through unchanged.
func TypecheckEscapeGraph ¶
func TypecheckEscapeGraph(g *EscapeGraph) error
TypecheckEscapeGraph determines whether its argument is type-correct. If a problem is found, a non-nil error is returned describing the problem. This function is advisory only; it will be unsound when the program uses e.g. unsafe constructs, and incomplete in that it will not check all possible ill-typed constructs. It is instead intended to aid debugging by isolating type errors to the place(s) where they are first introduced.
Types ¶
type Edge ¶
type Edge struct {
// contains filtered or unexported fields
}
Edge represents a single atomic edge within the escape graph. Nodes connected by more than one kind of edge will produce multiple Edge's when queried.
type EscapeGraph ¶
type EscapeGraph struct {
// contains filtered or unexported fields
}
EscapeGraph is the element of the monotone framework and the primary focus of the escape analysis. The graph represents edges as src -> dest -> isInternal. The final bool is semantically significant: the edges are labeled as internal or external. Escaped is a set of nodes that are not known to be local in the current context; they are treated differently on load operations. Leaked is a subset of escaped nodes that have (possibly) leaked out of the current goroutine, whereas escaped nodes may still be local depending on the calling context. The major operations on escape graphs are to AddEdge()s, (plus composite operations like Load, WeakAssign), Merge(), and compare with Matches().
func EscapeSummary ¶
func EscapeSummary(f *ssa.Function) (graph *EscapeGraph)
EscapeSummary computes the escape summary for a single function, independently of all other functions. Other functions are treated as arbitrary.
func NewEmptyEscapeGraph ¶
func NewEmptyEscapeGraph(nodes *NodeGroup) *EscapeGraph
NewEmptyEscapeGraph produces an empty graph, which is also the unit of Merge() below
func (*EscapeGraph) AddEdge ¶
func (g *EscapeGraph) AddEdge(src *Node, dest *Node, newFlag edgeFlags) (changed bool)
AddEdge adds an edge from base to dest. isInternal (usually `true`) signals whether this is an internal edge (created during the current function) or external edge (possibly existed before the current function).
func (*EscapeGraph) AddNode ¶
func (g *EscapeGraph) AddNode(n *Node) (changed bool)
AddNode ensures g has an entry for node n.
func (*EscapeGraph) AnalogousSubnode ¶
func (g *EscapeGraph) AnalogousSubnode(base *Node, subnode *Node) *Node
AnalogousSubnode returns the subnode of base that has the same relationship with base that subnode has with its parent. Typically used to copy fields. For implementation subnodes, if base is not abstract (i.e. can't have subnodes), the result will be either the base node itself or nil, depending on whether the types match.
func (*EscapeGraph) Call ¶
func (g *EscapeGraph) Call(pre *EscapeGraph, receiver *Node, args []*Node, freeVars []*Node, rets []*Node, callee *EscapeGraph)
Call computes the result of splicing in the summary (callee) of the callee's graph. args are the nodes corresponding to the caller's actual parameters at the callsite (nil if not pointer-like). rets are the nodes corresponding to the caller values to assign the results to (nil if not pointer-like). callee is the summary of the called function.
func (*EscapeGraph) CallUnknown ¶
func (g *EscapeGraph) CallUnknown(args []*Node, rets []*Node, funcName string)
CallUnknown computes the result of calling an unknown function. An unknown function has no bound on its allowed semantics. This means that the arguments are assumed to leak, and the return value is treated similarly to a load node, except it can never be resolved with arguments like loads can be.
func (*EscapeGraph) Clone ¶
func (g *EscapeGraph) Clone() *EscapeGraph
Clone clones a graph, preserving node identities between the two graphs.
func (*EscapeGraph) CloneReachable ¶
func (g *EscapeGraph) CloneReachable(roots []*Node) *EscapeGraph
CloneReachable clones an escape graph, but only preserving the nodes that are reachable from roots.
func (*EscapeGraph) Edges ¶
func (g *EscapeGraph) Edges(src, dest *Node, mask edgeFlags) []*Edge
Edges (s, d, mask) finds all the edges from s to d that match the bitflags in mask. Either or s or d may be nil, in which case they act as a wild card. To find all the edges from src to all nodes via only internal edges, do:
g.Edges(src, nil, EdgeInternal).
To iterate over the result, use a loop like:
for _, e := range g.Edges(src, nil, EdgeInternal) {
fmt.Printf("Found %v", e.dest)
}
If the mask is zero, the result will always be empty. This method is convenient, but may not be the most efficient.
func (*EscapeGraph) EnsureLoadNode ¶
EnsureLoadNode makes sure that if base is not local, then it has a node it points to. This can either be a new load node attached to base, or an existing node if the loadOp already created a load node somewhere in the base's history (this prevents infinite graphs). Regardless, the base node has an out-edge to this node. The node is returned, but there may be multiple external out-edges, and generally the specified load node should not be treated specially.
func (*EscapeGraph) FieldSubnode ¶
FieldSubnode returns the singular field subnode of `base`, with label `field`. The type tp is a hint for the type to apply to the new node.
func (*EscapeGraph) Graphviz ¶
func (g *EscapeGraph) Graphviz() string
Graphviz returns a (multi-line string) dot/graphviz input describing the graph.
func (*EscapeGraph) ImplementationSubnode ¶
func (g *EscapeGraph) ImplementationSubnode(base *Node, concreteTp types.Type) *Node
ImplementationSubnode returns the singular implementation subnode of `base`, with a given concrete type.
func (*EscapeGraph) IsSubnode ¶
func (g *EscapeGraph) IsSubnode(n *Node) bool
IsSubnode returns true if n is a subnode of some other node.
func (*EscapeGraph) IsSubnodeEdge ¶
func (g *EscapeGraph) IsSubnodeEdge(base, n *Node) bool
IsSubnodeEdge returns whether base and n have a subnode relationship, from base to n. There may also be other edges between these two nodes.
func (*EscapeGraph) LessEqual ¶
func (g *EscapeGraph) LessEqual(h *EscapeGraph) (isLessEq bool, reason string)
LessEqual returns true if g is less than or equal to h in the lattice ordering associated with the monotone framework. This function is useful for detecting convergence problems and correctness bugs.
func (*EscapeGraph) LoadField ¶
func (g *EscapeGraph) LoadField(valNode *Node, addrNode *Node, loadOp any, field string, tp types.Type)
LoadField applies the load operation `valNode = *addrNode[.field]` and modifies g. This is a generalized operation: it also applies to reading the specified field from slices, maps, globals, etc. If field is empty (""), then dereference the object itself, otherwise dereference only the specified field. generateLoadNode is called to lazily create a node if the load can happen against an external object; this can't always be determined a priori, and we don't want to create a load node unless necessary.
func (*EscapeGraph) Matches ¶
func (g *EscapeGraph) Matches(h *EscapeGraph) bool
Matches checks if two graphs are equal. Used for convergence checking.
func (*EscapeGraph) Merge ¶
func (g *EscapeGraph) Merge(h *EscapeGraph)
Merge computes the union of this graph with another, used at e.g. the join-points of a dataflow graph. Modifies g in-place.
func (*EscapeGraph) MergeNodeStatus ¶
func (g *EscapeGraph) MergeNodeStatus(n *Node, s EscapeStatus, rationale *dataflow.EscapeRationale)
MergeNodeStatus sets the status of n to at least s. Doesn't modify the status if the current status is greater equal to s. Modifies g.
func (*EscapeGraph) Pointees ¶
func (g *EscapeGraph) Pointees(src *Node) map[*Node]struct{}
Pointees returns the set of nodes (as a map to empty struct) that are pointed to by src by any type of direct edge.
func (*EscapeGraph) StoreField ¶
func (g *EscapeGraph) StoreField(addrNode, valNode *Node, field string, tp types.Type)
StoreField applies the effect of storing the pointer-like value valNode into the field of object(s) pointed to by addrNode. Generalizes to include map updates (m[k] = v), channel sends, and other operations that need to write to a specific "field" of the pointees of addr. If the field is empty (""), writes to the object itself.
func (*EscapeGraph) WeakAssign ¶
func (g *EscapeGraph) WeakAssign(dest *Node, src *Node)
WeakAssign applies the weak-assignment operation `dest = src`. Basically, ensures that dest points to whatever src points to. Weak here means that it does not erase any existing edges from dest. Handles subnodes recursively, so it works for structure types, but does not generate load nodes (thus weak assign is only valid for src's that are local, such as ValueNodes). See also `copyStruct()`.
type EscapeStatus ¶
type EscapeStatus uint8
EscapeStatus represents whether a node is Local, Escaped, or Leaked
const ( // Local status indicates the value has not escaped Local EscapeStatus = 0 // Escaped status indicates the value has escaped Escaped EscapeStatus = 1 // Leaked status indicates the value has leaked Leaked EscapeStatus = 2 )
type FunctionImplType ¶
type FunctionImplType struct {
// contains filtered or unexported fields
}
FunctionImplType represents the pointee of a function pointer
func (*FunctionImplType) String ¶
func (t *FunctionImplType) String() string
func (*FunctionImplType) Underlying ¶
func (t *FunctionImplType) Underlying() types.Type
Underlying returns the underlying type of the function implementation type
type ImplType ¶
type ImplType struct {
// contains filtered or unexported fields
}
ImplType represents the pointee of a map, channel, or interface
func (*ImplType) Underlying ¶
Underlying returns the underlying type of the implementation type
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
A Node represents the objects tracked by the escape analysis. Nodes represent local variables, globals, parameters, and heap cells of various kinds (maps, slices, arrays, structs)
func (*Node) IntrinsicEscape ¶
func (n *Node) IntrinsicEscape() EscapeStatus
IntrinsicEscape returns the intrinsic status of a node. Certain nodes are intrinsically external: parameters, loads, and globals. Note that this doesn't include ParamVars, which are the (local) pointers at the external objects. Other nodes are intrinsically escaped, as they represent parameters.
type NodeGroup ¶
type NodeGroup struct {
// contains filtered or unexported fields
}
A NodeGroup stores the identity of nodes within a current function context, and ensures that e.g. a single load node is shared between all invocations of a load instruction, or all allocations in a particular function.
func NewNodeGroup ¶
func NewNodeGroup(globalNodes *globalNodeGroup) *NodeGroup
NewNodeGroup returns a fresh node group that is tied to the underlying global group. Node groups with the same global node group may interact by sharing foreign nodes, but interactions across globalNodeGroups leads to unspecified behavior.
func (*NodeGroup) AddForeignNode ¶
AddForeignNode adds a foreign node to the node group. This currently just tracks which nodes are added so they can be iterated over. A different design would be to create a new node so that each NodeGroup is self-contained.
func (*NodeGroup) AllocNode ¶
AllocNode creates a node that represents an allocation, such as &S{}, make([]int, 3), map[int]int{}, etc.
func (*NodeGroup) IndexedAllocNode ¶
IndexedAllocNode creates a node that represents an allocation. It is similar to AllocNode, but allows more than one allocated node per instruction, keyed by an additional index string.
func (*NodeGroup) LoadNode ¶
LoadNode creates a load node, which represents the object(s) that are potentially reached through some load-like operation, e.g. *ptr, map[key], etc.
func (*NodeGroup) NewNode ¶
NewNode returns an entirely new node with the defined fields, and the given type hint
func (*NodeGroup) NilNode ¶
NilNode returns the nil node of a function, which represents a pointer that is always nil Invariant: should not have any out edges (i.e. should never be assigned to)
func (*NodeGroup) ParamNode ¶
ParamNode creates a node for the initial pointee of a parameter/freevar. This is different from the var node of the pointer, which exists for consistency with SSA values
func (*NodeGroup) ReturnNode ¶
ReturnNode returns the indexed return node of a function, which represents all the implicit or explicit variables that capture the returned values. There is one node per function return slot.
func (*NodeGroup) UnknownReturnNode ¶
UnknownReturnNode represents the return value of an unknown (unanalyzed) function. This is different from the return of a function that doesn't have a summary yet; this is for functions that will never be summarized. This should be fairly rare, as it is very conservative for soundness; functions should either be analyzed or have a manual summary written for them.
func (*NodeGroup) UnusedNode ¶
UnusedNode returns the unused pointer node, which represents a node that you don't care about. Can be used to represent the `_` identifier. Can have out edges, but these edges should never be used because nothing will read from `_`.
type ProgramAnalysisState ¶
type ProgramAnalysisState struct {
// contains filtered or unexported fields
}
ProgramAnalysisState contains the summaries for the entire program. Currently, this is just a simple wrapper around a map of function to analysis results, but it will likely need to expand to work with the taint analysis.
func EscapeAnalysis ¶
EscapeAnalysis computes the bottom-up escape summaries of functions matching the package filter.
Source Files