escape

package
v0.2.0-alpha Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 14, 2024 License: Apache-2.0 Imports: 14 Imported by: 0

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

View Source 
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
)
View Source 
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 

func AddressOfType(t types.Type) types.Type

AddressOfType computes what type would point to a given type. It is roughly the inverse of NillableDerefType.

func AsImplInterfaceType 

func AsImplInterfaceType(a types.Type) types.Type

AsImplInterfaceType returns the corresponding interface type, if the input is is an abstract interface implementation type, otherwise it returns nil.

func CanPointTo 

func CanPointTo(a, b types.Type) bool

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 

func ChannelContentsType(t types.Type) types.Type

ChannelContentsType gives the type of the contents of a channel. No-op otherwise

func CompatibleTypes 

func CompatibleTypes(tpA, tpB types.Type) (r bool)

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 

func InitializeEscapeAnalysisState(state *dataflow.AnalyzerState) error

InitializeEscapeAnalysisState initializes the escape analysis' state inside the dataflow state Returns an error if an error is encountered during the escape analysis.

func IsAbstractType 

func IsAbstractType(tp types.Type) (r bool)

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 

func IsEscapeTracked(t types.Type) bool

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 

func NillableDerefType(t types.Type) types.Type

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 

func (g *EscapeGraph) EnsureLoadNode(loadOp any, tp types.Type, base *Node) *Node

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 

func (g *EscapeGraph) FieldSubnode(base *Node, field string, tp types.Type) *Node

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) String 

func (t *ImplType) String() string

func (*ImplType) Underlying 

func (t *ImplType) Underlying() types.Type

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.

func (*Node) String 

func (n *Node) String() string

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 

func (g *NodeGroup) AddForeignNode(n *Node) (changed bool)

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 

func (g *NodeGroup) AllocNode(instr ssa.Instruction, t types.Type) *Node

AllocNode creates a node that represents an allocation, such as &S{}, make([]int, 3), map[int]int{}, etc.

func (*NodeGroup) IndexedAllocNode 

func (g *NodeGroup) IndexedAllocNode(instr ssa.Instruction, index string, t types.Type) *Node

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 

func (g *NodeGroup) LoadNode(location any, instr ssa.Instruction, t types.Type) *Node

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 

func (g *NodeGroup) NewNode(kind nodeKind, debug string, tp types.Type) *Node

NewNode returns an entirely new node with the defined fields, and the given type hint

func (*NodeGroup) NilNode 

func (g *NodeGroup) NilNode() *Node

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 

func (g *NodeGroup) ParamNode(param ssa.Value) *Node

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 

func (g *NodeGroup) ReturnNode(i int, t types.Type) *Node

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 

func (g *NodeGroup) UnknownReturnNode(funcName string) *Node

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 

func (g *NodeGroup) UnusedNode() *Node

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 `_`.

func (*NodeGroup) ValueNode 

func (g *NodeGroup) ValueNode(variable ssa.Value) *Node

ValueNode returns a node that represents a ssa.Value. Most such values are virtual registers created by instructions, e.g. the t1 in `t1 = *t0`.

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 

func EscapeAnalysis(state *dataflow.AnalyzerState, root *callgraph.Node) (*ProgramAnalysisState, error)

EscapeAnalysis computes the bottom-up escape summaries of functions matching the package filter.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.