diff options
Diffstat (limited to 'src/cmd/gc/esc.c')
-rw-r--r-- | src/cmd/gc/esc.c | 805 |
1 files changed, 805 insertions, 0 deletions
diff --git a/src/cmd/gc/esc.c b/src/cmd/gc/esc.c new file mode 100644 index 000000000..2614b5f35 --- /dev/null +++ b/src/cmd/gc/esc.c @@ -0,0 +1,805 @@ +// Copyright 2011 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. +// +// Escape analysis. +// +// First escfunc, esc and escassign recurse over the ast of each +// function to dig out flow(dst,src) edges between any +// pointer-containing nodes and store them in dst->escflowsrc. For +// variables assigned to a variable in an outer scope or used as a +// return value, they store a flow(theSink, src) edge to a fake node +// 'the Sink'. For variables referenced in closures, an edge +// flow(closure, &var) is recorded and the flow of a closure itself to +// an outer scope is tracked the same way as other variables. +// +// Then escflood walks the graph starting at theSink and tags all +// variables of it can reach an & node as escaping and all function +// parameters it can reach as leaking. +// +// If a value's address is taken but the address does not escape, +// then the value can stay on the stack. If the value new(T) does +// not escape, then new(T) can be rewritten into a stack allocation. +// The same is true of slice literals. +// +// If escape analysis is disabled (-s), this code is not used. +// Instead, the compiler assumes that any value whose address +// is taken without being immediately dereferenced +// needs to be moved to the heap, and new(T) and slice +// literals are always real allocations. + +#include <u.h> +#include <libc.h> +#include "go.h" + +static void escfunc(Node *func); +static void esclist(NodeList *l); +static void esc(Node *n); +static void escloopdepthlist(NodeList *l); +static void escloopdepth(Node *n); +static void escassign(Node *dst, Node *src); +static void esccall(Node*); +static void escflows(Node *dst, Node *src); +static void escflood(Node *dst); +static void escwalk(int level, Node *dst, Node *src); +static void esctag(Node *func); + +// Fake node that all +// - return values and output variables +// - parameters on imported functions not marked 'safe' +// - assignments to global variables +// flow to. +static Node theSink; + +static NodeList* dsts; // all dst nodes +static int loopdepth; // for detecting nested loop scopes +static int pdepth; // for debug printing in recursions. +static Strlit* safetag; // gets slapped on safe parameters' field types for export +static int dstcount, edgecount; // diagnostic +static NodeList* noesc; // list of possible non-escaping nodes, for printing + +void +escapes(NodeList *all) +{ + NodeList *l; + + theSink.op = ONAME; + theSink.orig = &theSink; + theSink.class = PEXTERN; + theSink.sym = lookup(".sink"); + theSink.escloopdepth = -1; + + safetag = strlit("noescape"); + noesc = nil; + + // flow-analyze functions + for(l=all; l; l=l->next) + if(l->n->op == ODCLFUNC || l->n->op == OCLOSURE) + escfunc(l->n); + + // print("escapes: %d dsts, %d edges\n", dstcount, edgecount); + + // visit the updstream of each dst, mark address nodes with + // addrescapes, mark parameters unsafe + for(l = dsts; l; l=l->next) + escflood(l->n); + + // for all top level functions, tag the typenodes corresponding to the param nodes + for(l=all; l; l=l->next) + if(l->n->op == ODCLFUNC) + esctag(l->n); + + if(debug['m']) { + for(l=noesc; l; l=l->next) + if(l->n->esc == EscNone) + warnl(l->n->lineno, "%S %hN does not escape", + (l->n->curfn && l->n->curfn->nname) ? l->n->curfn->nname->sym : S, + l->n); + } +} + + +static void +escfunc(Node *func) +{ + Node *savefn, *n; + NodeList *ll; + int saveld; + + saveld = loopdepth; + loopdepth = 1; + savefn = curfn; + curfn = func; + + for(ll=curfn->dcl; ll; ll=ll->next) { + if(ll->n->op != ONAME) + continue; + switch (ll->n->class) { + case PPARAMOUT: + // output parameters flow to the sink + escflows(&theSink, ll->n); + ll->n->escloopdepth = loopdepth; + break; + case PPARAM: + if(ll->n->type && !haspointers(ll->n->type)) + break; + ll->n->esc = EscNone; // prime for escflood later + noesc = list(noesc, ll->n); + ll->n->escloopdepth = loopdepth; + break; + } + } + + // walk will take the address of cvar->closure later and assign it to cvar. + // handle that here by linking a fake oaddr node directly to the closure. + for(ll=curfn->cvars; ll; ll=ll->next) { + if(ll->n->op == OXXX) // see dcl.c:398 + continue; + + n = nod(OADDR, ll->n->closure, N); + n->lineno = ll->n->lineno; + typecheck(&n, Erv); + escassign(curfn, n); + } + + escloopdepthlist(curfn->nbody); + esclist(curfn->nbody); + curfn = savefn; + loopdepth = saveld; +} + +// Mark labels that have no backjumps to them as not increasing loopdepth. +// Walk hasn't generated (goto|label)->left->sym->label yet, so we'll cheat +// and set it to one of the following two. Then in esc we'll clear it again. +static Label looping; +static Label nonlooping; + +static void +escloopdepthlist(NodeList *l) +{ + for(; l; l=l->next) + escloopdepth(l->n); +} + +static void +escloopdepth(Node *n) +{ + if(n == N) + return; + + escloopdepthlist(n->ninit); + + switch(n->op) { + case OLABEL: + if(!n->left || !n->left->sym) + fatal("esc:label without label: %+N", n); + // Walk will complain about this label being already defined, but that's not until + // after escape analysis. in the future, maybe pull label & goto analysis out of walk and put before esc + // if(n->left->sym->label != nil) + // fatal("escape analysis messed up analyzing label: %+N", n); + n->left->sym->label = &nonlooping; + break; + case OGOTO: + if(!n->left || !n->left->sym) + fatal("esc:goto without label: %+N", n); + // If we come past one that's uninitialized, this must be a (harmless) forward jump + // but if it's set to nonlooping the label must have preceded this goto. + if(n->left->sym->label == &nonlooping) + n->left->sym->label = &looping; + break; + } + + escloopdepth(n->left); + escloopdepth(n->right); + escloopdepthlist(n->list); + escloopdepth(n->ntest); + escloopdepth(n->nincr); + escloopdepthlist(n->nbody); + escloopdepthlist(n->nelse); + escloopdepthlist(n->rlist); + +} + +static void +esclist(NodeList *l) +{ + for(; l; l=l->next) + esc(l->n); +} + +static void +esc(Node *n) +{ + int lno; + NodeList *ll, *lr; + + if(n == N) + return; + + lno = setlineno(n); + + if(n->op == OFOR || n->op == ORANGE) + loopdepth++; + + esc(n->left); + esc(n->right); + esc(n->ntest); + esc(n->nincr); + esclist(n->ninit); + esclist(n->nbody); + esclist(n->nelse); + esclist(n->list); + esclist(n->rlist); + + if(n->op == OFOR || n->op == ORANGE) + loopdepth--; + + if(debug['m'] > 1) + print("%L:[%d] %S esc: %N\n", lineno, loopdepth, + (curfn && curfn->nname) ? curfn->nname->sym : S, n); + + switch(n->op) { + case ODCL: + // Record loop depth at declaration. + if(n->left) + n->left->escloopdepth = loopdepth; + break; + + case OLABEL: + if(n->left->sym->label == &nonlooping) { + if(debug['m'] > 1) + print("%L:%N non-looping label\n", lineno, n); + } else if(n->left->sym->label == &looping) { + if(debug['m'] > 1) + print("%L: %N looping label\n", lineno, n); + loopdepth++; + } + // See case OLABEL in escloopdepth above + // else if(n->left->sym->label == nil) + // fatal("escape anaylysis missed or messed up a label: %+N", n); + + n->left->sym->label = nil; + + case ORANGE: + // Everything but fixed array is a dereference. + if(isfixedarray(n->type) && n->list->next) + escassign(n->list->next->n, n->right); + break; + + case OSWITCH: + if(n->ntest && n->ntest->op == OTYPESW) { + for(ll=n->list; ll; ll=ll->next) { // cases + // ntest->right is the argument of the .(type), + // ll->n->nname is the variable per case + escassign(ll->n->nname, n->ntest->right); + } + } + break; + + case OAS: + case OASOP: + escassign(n->left, n->right); + break; + + case OAS2: // x,y = a,b + if(count(n->list) == count(n->rlist)) + for(ll=n->list, lr=n->rlist; ll; ll=ll->next, lr=lr->next) + escassign(ll->n, lr->n); + break; + + case OAS2RECV: // v, ok = <-ch + case OAS2MAPR: // v, ok = m[k] + case OAS2DOTTYPE: // v, ok = x.(type) + escassign(n->list->n, n->rlist->n); + break; + + case OSEND: // ch <- x + escassign(&theSink, n->right); + break; + + case ODEFER: + if(loopdepth == 1) // top level + break; + // arguments leak out of scope + // TODO: leak to a dummy node instead + // fallthrough + case OPROC: + // go f(x) - f and x escape + escassign(&theSink, n->left->left); + escassign(&theSink, n->left->right); // ODDDARG for call + for(ll=n->left->list; ll; ll=ll->next) + escassign(&theSink, ll->n); + break; + + case ORETURN: + for(ll=n->list; ll; ll=ll->next) + escassign(&theSink, ll->n); + break; + + case OPANIC: + // Argument could leak through recover. + escassign(&theSink, n->left); + break; + + case OAPPEND: + if(!n->isddd) + for(ll=n->list->next; ll; ll=ll->next) + escassign(&theSink, ll->n); // lose track of assign to dereference + break; + + case OCALLMETH: + case OCALLFUNC: + case OCALLINTER: + esccall(n); + break; + + case OCONV: + case OCONVNOP: + case OCONVIFACE: + escassign(n, n->left); + break; + + case OARRAYLIT: + if(isslice(n->type)) { + n->esc = EscNone; // until proven otherwise + noesc = list(noesc, n); + n->escloopdepth = loopdepth; + // Values make it to memory, lose track. + for(ll=n->list; ll; ll=ll->next) + escassign(&theSink, ll->n->right); + } else { + // Link values to array. + for(ll=n->list; ll; ll=ll->next) + escassign(n, ll->n->right); + } + break; + + case OSTRUCTLIT: + // Link values to struct. + for(ll=n->list; ll; ll=ll->next) + escassign(n, ll->n->right); + break; + + case OPTRLIT: + n->esc = EscNone; // until proven otherwise + noesc = list(noesc, n); + n->escloopdepth = loopdepth; + // Contents make it to memory, lose track. + escassign(&theSink, n->left); + break; + + case OMAPLIT: + n->esc = EscNone; // until proven otherwise + noesc = list(noesc, n); + n->escloopdepth = loopdepth; + // Keys and values make it to memory, lose track. + for(ll=n->list; ll; ll=ll->next) { + escassign(&theSink, ll->n->left); + escassign(&theSink, ll->n->right); + } + break; + + case OADDR: + case OCLOSURE: + case OMAKECHAN: + case OMAKEMAP: + case OMAKESLICE: + case ONEW: + n->escloopdepth = loopdepth; + n->esc = EscNone; // until proven otherwise + noesc = list(noesc, n); + break; + } + + lineno = lno; +} + +// Assert that expr somehow gets assigned to dst, if non nil. for +// dst==nil, any name node expr still must be marked as being +// evaluated in curfn. For expr==nil, dst must still be examined for +// evaluations inside it (e.g *f(x) = y) +static void +escassign(Node *dst, Node *src) +{ + int lno; + + if(isblank(dst) || dst == N || src == N || src->op == ONONAME || src->op == OXXX) + return; + + if(debug['m'] > 1) + print("%L:[%d] %S escassign: %hN = %hN\n", lineno, loopdepth, + (curfn && curfn->nname) ? curfn->nname->sym : S, dst, src); + + setlineno(dst); + + // Analyze lhs of assignment. + // Replace dst with theSink if we can't track it. + switch(dst->op) { + default: + dump("dst", dst); + fatal("escassign: unexpected dst"); + + case OARRAYLIT: + case OCLOSURE: + case OCONV: + case OCONVIFACE: + case OCONVNOP: + case OMAPLIT: + case OSTRUCTLIT: + break; + + case ONAME: + if(dst->class == PEXTERN) + dst = &theSink; + break; + case ODOT: // treat "dst.x = src" as "dst = src" + escassign(dst->left, src); + return; + case OINDEX: + if(isfixedarray(dst->left->type)) { + escassign(dst->left, src); + return; + } + dst = &theSink; // lose track of dereference + break; + case OIND: + case ODOTPTR: + dst = &theSink; // lose track of dereference + break; + case OINDEXMAP: + // lose track of key and value + escassign(&theSink, dst->right); + dst = &theSink; + break; + } + + lno = setlineno(src); + pdepth++; + + switch(src->op) { + case OADDR: // dst = &x + case OIND: // dst = *x + case ODOTPTR: // dst = (*x).f + case ONAME: + case OPARAM: + case ODDDARG: + case OPTRLIT: + case OARRAYLIT: + case OMAPLIT: + case OSTRUCTLIT: + // loopdepth was set in the defining statement or function header + escflows(dst, src); + break; + + case ODOT: + // A non-pointer escaping from a struct does not concern us. + if(src->type && !haspointers(src->type)) + break; + // fallthrough + case OCONV: + case OCONVIFACE: + case OCONVNOP: + case ODOTMETH: // treat recv.meth as a value with recv in it, only happens in ODEFER and OPROC + // iface.method already leaks iface in esccall, no need to put in extra ODOTINTER edge here + case ODOTTYPE: + case ODOTTYPE2: + case OSLICE: + case OSLICEARR: + // Conversions, field access, slice all preserve the input value. + escassign(dst, src->left); + break; + + case OAPPEND: + // Append returns first argument. + escassign(dst, src->list->n); + break; + + case OINDEX: + // Index of array preserves input value. + if(isfixedarray(src->left->type)) + escassign(dst, src->left); + break; + + case OMAKECHAN: + case OMAKEMAP: + case OMAKESLICE: + case ONEW: + escflows(dst, src); + break; + + case OCLOSURE: + escflows(dst, src); + escfunc(src); + break; + + case OADD: + case OSUB: + case OOR: + case OXOR: + case OMUL: + case ODIV: + case OMOD: + case OLSH: + case ORSH: + case OAND: + case OANDNOT: + case OPLUS: + case OMINUS: + case OCOM: + // Might be pointer arithmetic, in which case + // the operands flow into the result. + // TODO(rsc): Decide what the story is here. This is unsettling. + escassign(dst, src->left); + escassign(dst, src->right); + break; + + } + + pdepth--; + lineno = lno; +} + + +// This is a bit messier than fortunate, pulled out of escassign's big +// switch for clarity. We either have the paramnodes, which may be +// connected to other things throug flows or we have the parameter type +// nodes, which may be marked 'n(ofloworescape)'. Navigating the ast is slightly +// different for methods vs plain functions and for imported vs +// this-package +static void +esccall(Node *n) +{ + NodeList *ll, *lr; + Node *a, *fn, *src; + Type *t, *fntype; + + fn = N; + switch(n->op) { + default: + fatal("esccall"); + + case OCALLFUNC: + fn = n->left; + fntype = fn->type; + break; + + case OCALLMETH: + fn = n->left->right->sym->def; + if(fn) + fntype = fn->type; + else + fntype = n->left->type; + break; + + case OCALLINTER: + fntype = n->left->type; + break; + } + + ll = n->list; + if(n->list != nil && n->list->next == nil) { + a = n->list->n; + if(a->type->etype == TSTRUCT && a->type->funarg) { + // f(g()). + // Since f's arguments are g's results and + // all function results escape, we're done. + ll = nil; + } + } + + if(fn && fn->op == ONAME && fn->class == PFUNC && fn->defn && fn->defn->nbody && fn->ntype) { + // Local function. Incorporate into flow graph. + + // Receiver. + if(n->op != OCALLFUNC) + escassign(fn->ntype->left->left, n->left->left); + + for(lr=fn->ntype->list; ll && lr; ll=ll->next, lr=lr->next) { + src = ll->n; + if(lr->n->isddd && !n->isddd) { + // Introduce ODDDARG node to represent ... allocation. + src = nod(ODDDARG, N, N); + src->escloopdepth = loopdepth; + src->lineno = n->lineno; + src->esc = EscNone; // until we find otherwise + noesc = list(noesc, src); + n->right = src; + } + if(lr->n->left != N) + escassign(lr->n->left, src); + if(src != ll->n) + break; + } + // "..." arguments are untracked + for(; ll; ll=ll->next) + escassign(&theSink, ll->n); + return; + } + + // Imported function. Use the escape tags. + if(n->op != OCALLFUNC) { + t = getthisx(fntype)->type; + if(!t->note || strcmp(t->note->s, safetag->s) != 0) + escassign(&theSink, n->left->left); + } + for(t=getinargx(fntype)->type; ll; ll=ll->next) { + src = ll->n; + if(t->isddd && !n->isddd) { + // Introduce ODDDARG node to represent ... allocation. + src = nod(ODDDARG, N, N); + src->escloopdepth = loopdepth; + src->lineno = n->lineno; + src->esc = EscNone; // until we find otherwise + noesc = list(noesc, src); + n->right = src; + } + if(!t->note || strcmp(t->note->s, safetag->s) != 0) + escassign(&theSink, src); + if(src != ll->n) + break; + t = t->down; + } + // "..." arguments are untracked + for(; ll; ll=ll->next) + escassign(&theSink, ll->n); +} + +// Store the link src->dst in dst, throwing out some quick wins. +static void +escflows(Node *dst, Node *src) +{ + if(dst == nil || src == nil || dst == src) + return; + + // Don't bother building a graph for scalars. + if(src->type && !haspointers(src->type)) + return; + + if(debug['m']>2) + print("%L::flows:: %hN <- %hN\n", lineno, dst, src); + + if(dst->escflowsrc == nil) { + dsts = list(dsts, dst); + dstcount++; + } + edgecount++; + + dst->escflowsrc = list(dst->escflowsrc, src); +} + +// Whenever we hit a reference node, the level goes up by one, and whenever +// we hit an OADDR, the level goes down by one. as long as we're on a level > 0 +// finding an OADDR just means we're following the upstream of a dereference, +// so this address doesn't leak (yet). +// If level == 0, it means the /value/ of this node can reach the root of this flood. +// so if this node is an OADDR, it's argument should be marked as escaping iff +// it's currfn/loopdepth are different from the flood's root. +// Once an object has been moved to the heap, all of it's upstream should be considered +// escaping to the global scope. +static void +escflood(Node *dst) +{ + NodeList *l; + + switch(dst->op) { + case ONAME: + case OCLOSURE: + break; + default: + return; + } + + if(debug['m']>1) + print("\nescflood:%d: dst %hN scope:%S[%d]\n", walkgen, dst, + (dst->curfn && dst->curfn->nname) ? dst->curfn->nname->sym : S, + dst->escloopdepth); + + for(l = dst->escflowsrc; l; l=l->next) { + walkgen++; + escwalk(0, dst, l->n); + } +} + +static void +escwalk(int level, Node *dst, Node *src) +{ + NodeList *ll; + int leaks; + + if(src->walkgen == walkgen) + return; + src->walkgen = walkgen; + + if(debug['m']>1) + print("escwalk: level:%d depth:%d %.*s %hN scope:%S[%d]\n", + level, pdepth, pdepth, "\t\t\t\t\t\t\t\t\t\t", src, + (src->curfn && src->curfn->nname) ? src->curfn->nname->sym : S, src->escloopdepth); + + pdepth++; + + leaks = (level <= 0) && (dst->escloopdepth < src->escloopdepth); + + switch(src->op) { + case ONAME: + if(src->class == PPARAM && leaks && src->esc == EscNone) { + src->esc = EscScope; + if(debug['m']) + warnl(src->lineno, "leaking param: %hN", src); + } + break; + + case OPTRLIT: + case OADDR: + if(leaks) { + src->esc = EscHeap; + addrescapes(src->left); + if(debug['m']) + warnl(src->lineno, "%hN escapes to heap", src); + } + escwalk(level-1, dst, src->left); + break; + + case OARRAYLIT: + if(isfixedarray(src->type)) + break; + // fall through + case ODDDARG: + case OMAKECHAN: + case OMAKEMAP: + case OMAKESLICE: + case OMAPLIT: + case ONEW: + case OCLOSURE: + if(leaks) { + src->esc = EscHeap; + if(debug['m']) + warnl(src->lineno, "%hN escapes to heap", src); + } + break; + + case OINDEX: + if(isfixedarray(src->type)) + break; + // fall through + case OSLICE: + case ODOTPTR: + case OINDEXMAP: + case OIND: + escwalk(level+1, dst, src->left); + } + + for(ll=src->escflowsrc; ll; ll=ll->next) + escwalk(level, dst, ll->n); + + pdepth--; +} + +static void +esctag(Node *func) +{ + Node *savefn; + NodeList *ll; + + // External functions must be assumed unsafe. + if(func->nbody == nil) + return; + + savefn = curfn; + curfn = func; + + for(ll=curfn->dcl; ll; ll=ll->next) { + if(ll->n->op != ONAME || ll->n->class != PPARAM) + continue; + + switch (ll->n->esc) { + case EscNone: // not touched by escflood + if(haspointers(ll->n->type)) // don't bother tagging for scalars + ll->n->paramfld->note = safetag; + case EscHeap: // touched by escflood, moved to heap + case EscScope: // touched by escflood, value leaves scope + break; + } + } + + curfn = savefn; +} |