src/cmd/gc/esc.c - Issue 4634073: code review 4634073: gc: Escape analysis.

Side by Side Diff: src/cmd/gc/esc.c

Issue 4634073: code review 4634073: gc: Escape analysis. (Closed)

Patch Set: diff -r 1cad1e8470ba https://go.googlecode.com/hg/ Created 13 years, 9 months ago

Left:
Right:

Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.

Jump to:

View unified diff | Download patch

OLD	NEW
(Empty)
	1 // Copyright 2009 The Go Authors. All rights reserved.
	rsc 2011/07/01 17:43:35 new code, so 2011 new code, so 2011
	2 // Use of this source code is governed by a BSD-style

	3 // license that can be found in the LICENSE file.

	4 //

	5 // Theory of operation:

	6 // A variable must be moved to the heap (from the stack) if

	7 // it's address escapes the current function scope, meaning

	8 // - the address is taken (with the unary-& operator OADDR)

	9 // - AND this pointer value leaks outside the current function scope.

	10 //·

	11 // A (pointer) value leaks if and only if any of the following happens

	12 // - it is assigned to (part of) a global variable (class PEXTERN)

	13 // part-of can mean: struct member, array or slice element,

	14 // sent on channel, map key or value.

	15 // * in case of doubt, e.g. if the lhs of the assignment is

	16 // a pointer indirection, we have to assume the rhs leaks.

	17 // - it is returned from a function (== assigned to an out-parameter)

	18 // - it is passed to a function as the this- or input parameter,

	19 // AND this parameter itself leaks from its function scope

	20 // * in case of doubt, e.g. if the function is not a named one

	21 // but a func-typed variable, we have to assume it leaks.

	22 // - it is used in an expression inside a go (OPROC) statement

	23 // - it is assigned to (part of) a node that itself leaks

	24 //

	25 // Whether parameters leak or not is not different to analyse than any

	26 // other variable.

	27 //·

	28 // To find out the leak graph for pointer values (and arrays, slices,

	29 // maps and structs that contain them) escanalfunc walks the AST to

	30 // emit directed edges of 'leakage' between nodes, known leaks get an

	31 // edge to a fake node theSink. When the graph is complete, it is

	32 // traversed starting from theSink and any reachable node that is of

	33 // type OADDR will have it's argument marked for moving to the heap.

	34 //

	35 // Note that this will cover the previously special case of * (pointer cast)(uns afe.Pointer(& x)):

	36 // OADDR x will leak all the way up to the top OREF and stop there, unless someo ne takes the OADDR of that again.

	37 // if i code it all up right that is.

	38

	39 #include "go.h"

	40

	41 static void eastmtlist(NodeList *l);

	42 static void eastmt(Node *n);

	43 static void eaexpr(Node dst, Node expr);

	44

	45 // Fake node that all return values, global variables and

	46 // goroutine-used variables leak to.

	47 static Node theSink;

	48

	49 void

	50 escanalfunc(Node *func)
	rsc 2011/07/01 17:43:35 sort of awkward. i suggest ,s/escanal/esc/ or s// sort of awkward. i suggest ,s/escanal/esc/ or s//escape/
	51 {

	52 curfn = func;

	53 // Walk the AST's to find the graph of src-leaksto-dst.

	54 eastmtlist(func->nbody);

	55 curfn = nil;

	56 }

	57

	58 void

	59 escanalfinish()

	60 {

	61 // walk the graph, mark nodes as 'leaking'

	62 // and move to heap any OADDR's arguments that do.

	63 }

	64

	65

	66 static int

	67 isinteresting(Type *t) {

	68

	69 if (t == T)

	70 fatal("no type for isinteresting");

	71

	72 switch(t->etype) {

	73 case TPTR32:

	74 case TPTR64:

	75 case TINTER:

	76 return 1;

	77 case TARRAY:

	78 case TCHAN:

	79 return isinteresting(t->type);

	80 case TMAP:

	81 return isinteresting(t->type) \|\| isinteresting(t->down);

	82 case TSTRUCT:

	83 for(t=t->type; t!=T; t=t->down) {

	84 if(t->etype != TFIELD)

	85 fatal("isinteresting: not TFIELD: %lT", t);

	86 if (isinteresting(t->type))

	87 return 1;

	88 }

	89 // fallthrough

	90 }

	91 return 0;

	92 }

	93

	94

	95 // Assert that leaking dst will cause expr to leak as well,
	rsc 2011/07/01 17:43:35 s/expr/n/ s/expr/n/
	96 // and check the parts of expr themselves for leakage.

	97 // examples:

	98 // dst = src assign to scalar

	99 // dst[idx] = src assign to array, slice or map element

	100 // dst[src] = ... assign to map key

	101 // dst <- src send to channel

	102 // dst.fld = src assign to struct field

	103 //

	104 static void

	105 eaexpr(Node dst, Node n)

	106 {

	107 NodeList *ll;

	108

	109 if(n == N \|\| n == dst)

	110 return;

	111

	112 setlineno(n);

	113

	114 if (n->trecur)

	115 return;

	116 n->trecur = 1;

	117

	118 if (n->typecheck == 0) {··

	119 dump("eaexpr missing typecheck", n);

	120 fatal("Missing typecheck.");

	121 }

	122

	123 // if dst is not interesting, save some work down the recursion

	124 if (dst != &theSink)

	125 if ((dst == N) \|\| isblank(dst) \|\| !isinteresting(dst->type))

	126 dst = N;

	127

	128 // here: turn dests x[k] into x, etc. see part-of in top comment

	129

	130 if (dst && dst != &theSink && !dst->type) dump("typeless dst", dst);

	131 ········

	132 if (dst && dst->op == ONAME && dst->class == PEXTERN)

	133 dst = &theSink;

	134

	135 if (dst != &theSink)

	136 print("%L %S::%#N <= %#N\n", lineno, curfn->nname->sym, dst, n);

	137 else

	138 print("%L %S:: leaks %#N\n", lineno, curfn->nname->sym, n);

	139

	140

	141 switch(n->op) {

	142 default:

	143 dump("eaexpr", n);

	144 fatal("eaexpr %O", n->op);

	145 break;

	146

	147 case OADDR:

	148 eaexpr(N, n->left);

	149 // fallthrough

	150 case ONAME:

	151 case OPARAM:

	152 case OCOMPLIT:

	153 case OMAPLIT:

	154 case OSTRUCTLIT:

	155 case OARRAYLIT:

	156 if (dst) dst->asrc = list(dst->asrc, n);

	157 break;

	158

	159 case OIND: // dst = *y

	160 eaexpr(N, n->left);

	161 break;

	162

	163 case OLITERAL:

	164 case ORECOVER:

	165 break;

	166

	167 // harmless unary

	168 case ONOT: case OCOM:

	169 case OCAP: case OLEN:

	170 case OREAL: case OIMAG:

	171 case OARRAYBYTESTR:

	172 case OARRAYRUNESTR:

	173 case OSTRARRAYBYTE:

	174 case OSTRARRAYRUNE:

	175 case ORUNESTR:

	176 eaexpr(N, n->left);

	177 break;

	178

	179 // harmless binary

	180 case OADD: case OAND: case OANDAND:

	181 case OANDNOT: case ODIV: case OEQ:

	182 case OGE: case OGT: case OLE:

	183 case OLT: case OLSH: case ORSH:

	184 case OMOD: case OMUL: case ONE:

	185 case OOR: case OOROR: case OSUB:

	186 case OXOR: case OADDSTR: case OASOP:

	187 case OCMPIFACE: case OCMPSTR: case OCOMPLEX:

	188 eaexpr(N, n->left);

	189 eaexpr(N, n->right);

	190 break;

	191

	192 // unaries that pass the value through

	193 case OCONV:

	194 case OCONVIFACE:

	195 case OCONVNOP:

	196 case ODOTTYPE:

	197 case ODOTTYPE2:

	198 case ORECV: // leaks the whole channel

	199 eaexpr(dst, n->left);

	200 break;

	201

	202 case OCOPY:

	203 // left leaks to right, but the return value is harmless

	204 eaexpr(n->left, n->right);

	205 break;

	206

	207 case OAPPEND:

	208 eaexpr(dst, n->list->n);

	209 for (ll=n->list->next; ll; ll=ll->next)

	210 eaexpr(n->list->n, ll->n);

	211 break;

	212

	213 // all arguments leak to the parameter nodes.

	214 // TODO ...when we figure out how to get our hands at them.

	215 case OCALLMETH:

	216 case OCALLINTER:

	217 eaexpr(&theSink, n->left->left); // DOTMETH->this or DOTINTER->t his

	218 // fallthrough

	219 case OCALLFUNC:

	220 for (ll=n->list; ll; ll=ll->next)

	221 eaexpr(&theSink , ll->n);

	222 break;

	223

	224 case ODOT:

	225 case ODOTPTR:

	226 // pretend all of the struct leaked

	227 // n->right is just an (untypechecked) ONAME

	228 eaexpr(dst, n->left);

	229 break;

	230

	231 case OSLICE: // the big thing leaks, the keys just need checking

	232 case OSLICEARR:

	233 case OSLICESTR:

	234 case OINDEX:···

	235 case OINDEXMAP:

	236 eaexpr(dst, n->left);

	237 eaexpr(N, n->right);

	238 break;

	239

	240 case OMAKECHAN:

	241 case OMAKEMAP:

	242 case OMAKESLICE:

	243 case ONEW: // first arg is type, all others need checking

	244 for (ll=n->list->next; ll; ll=ll->next)

	245 eaexpr(N, ll->n);

	246 if (dst) dst->asrc = list(dst->asrc, n); // but this is intere sting

	247 break;

	248

	249 break;

	250 }

	251

	252 n->trecur = 0;

	253 }

	254

	255 static void

	256 eastmtlist(NodeList* l)

	257 {

	258 for (; l; l = l->next)

	259 eastmt(l->n);

	260 }

	261

	262 static void

	263 eastmt(Node *n)

	264 {

	265 int cl, cr;

	266 NodeList ll, lr;

	267

	268 if(n == N)

	269 return;

	270

	271 if (n->trecur)

	272 return;

	273 n->trecur = 1;

	274

	275 setlineno(n);

	276

	277 if (n->typecheck == 0) {

	278 dump("eastmt missing typecheck", n);

	279 fatal("Missing typecheck.");

	280 }

	281

	282 switch(n->op) {

	283 default:

	284 // things i haven't thought of

	285 dump("eastmt", n);

	286 // fallthrough

	287 // things that shouldn't happen here

	288 case OCASE: case OXCASE:

	289 case OFALL:

	290 case OCALL:

	291 fatal("eastmt %O", n->op);

	292 break;

	293

	294 case ODCL:

	295 case ODCLCONST:

	296 case ODCLTYPE:

	297 case OBREAK:

	298 case OCONTINUE:

	299 case OXFALL:

	300 case OGOTO:

	301 case OLABEL:

	302 case OEMPTY:

	303 case OCLOSE:

	304 case OPRINT:

	305 case OPRINTN:

	306 // all harmless

	307 break;

	308

	309 case OBLOCK:

	310 eastmtlist(n->list);

	311 break;

	312

	313 case OFOR:

	314 eastmtlist(n->ninit);

	315 if(n->ntest != N) {

	316 eastmtlist(n->ntest->ninit);

	317 eaexpr(N, n->ntest);

	318 }

	319 eastmt(n->nincr);

	320 eastmtlist(n->nbody);

	321 break;

	322

	323 case ORANGE: // for <list> = range <right> { <nbody> }

	324 switch(n->type->etype) {

	325 case TARRAY: // i, v = range sliceorarrayorstring

	326 case TSTRING:

	327 if(n->list->next)

	328 eaexpr(n->list->next->n, n->right);

	329 break;··················

	330 case TMAP: // k, v = range map

	331 eaexpr(n->list->n, n->right);

	332 if(n->list->next)

	333 eaexpr(n->list->next->n, n->right);

	334 break;

	335 case TCHAN: // v = range chan

	336 eaexpr(n->list->n, n->right);

	337 break;

	338 }

	339 ········

	340 eastmtlist(n->nbody);

	341 break;

	342

	343 case OIF:

	344 eastmtlist(n->ninit);

	345 eaexpr(N, n->ntest);

	346 eastmtlist(n->nbody);

	347 eastmtlist(n->nelse);

	348 break;

	349

	350 case OSELECT:

	351 eastmtlist(n->ninit);

	352 for(ll=n->list; ll; ll=ll->next) { // todo what about the test?

	353 eastmt(ll->n->left);

	354 eastmtlist(ll->n->nbody);

	355 }

	356 break;

	357

	358 case OSELRECV2:

	359 case OSELRECV:

	360 eaexpr(n->left, n->right);

	361 break;

	362

	363 case OSWITCH:

	364 eastmtlist(n->ninit);

	365 if(n->ntest && n->ntest->op == OTYPESW) {

	366 eaexpr(n->ntest->left, n->ntest->right);

	367 for(ll=n->list; ll; ll=ll->next)

	368 eastmtlist(ll->n->nbody);

	369 } else {

	370 eaexpr(N, n->ntest);

	371 for(ll=n->list; ll; ll=ll->next) { // cases

	372 for (lr=ll->n->list; lr; lr=lr->next)

	373 eaexpr(N, lr->n);

	374 eastmtlist(ll->n->nbody);

	375 }

	376 }

	377 break;

	378

	379 case OAS:·

	380 case OASOP: // v += x etc. never applies to pointers, but l eave it to eaexpr to figure that out.

	381 eaexpr(n->left, n->right);

	382 break;

	383

	384 // escape analysis happens after typecheck, so the

	385 // OAS2xxx have already been substituted.

	386 case OAS2:

	387 cl = count(n->list);

	388 cr = count(n->rlist);

	389 if (cl > 1 && cr == 1) {

	390 for(ll=n->list; ll; ll=ll->next)

	391 eaexpr(ll->n, n->rlist->n);

	392 } else {·

	393 if(cl != cr)

	394 fatal("eastmt: bad OAS2: %N", n);

	395 for(ll=n->list, lr=n->rlist; ll; ll=ll->next, lr=lr->nex t)

	396 eaexpr(ll->n, lr->n);

	397 }

	398 break;

	399 ················

	400 case OAS2RECV: // v, ok = <-ch

	401 case OAS2MAPR: // v, ok = m[k]

	402 case OAS2DOTTYPE: // v, ok = x.(type)

	403 eaexpr(n->list->n, n->rlist->n->left);

	404 break;

	405

	406 case OAS2MAPW: // m[k] = x, ok

	407 eaexpr(n->list->n->left, n->rlist->n);

	408 break;

	409

	410 case ORECV: // unary <-ch as statement

	411 eaexpr(N, n->left);

	412 break;

	413

	414 case OSEND: // ch <- x

	415 eaexpr(n->left, n->right);

	416 break;

	417

	418 case OCOPY: // second arguments leaks to the first

	419 eaexpr(n->left, n->right);

	420 break;

	421

	422 case OAPPEND: // note: append also leaks all its args in an expression

	423 for (ll=n->list->next; ll; ll=ll->next)

	424 eaexpr(n->list->n, ll->n);

	425 break;

	426

	427 case OAS2FUNC: // x,y,z = f()

	428 // the return values already escape because they're return value s

	429 // no need to tie them to x, y or z here.

	430 eaexpr(N, n->rlist->n);

	431 break;

	432 ················

	433 case OCALLINTER:

	434 case OCALLFUNC:

	435 case OCALLMETH:

	436 n->trecur = 0;

	437 eaexpr(N, n);

	438 break;

	439

	440 case ODEFER:

	441 eastmt(n->left);

	442 break;

	443

	444 case ORETURN:

	445 for (ll=n->list; ll; ll=ll->next)

	446 eaexpr(&theSink, ll->n);

	447 break;

	448

	449 case OPROC: // n->left is a pseudocall, consider all arguments leaking

	450 for (ll=n->left->list; ll; ll=ll->next)

	451 eaexpr(&theSink, ll->n);

	452 break;

	453

	454 case OPANIC:

	455 // Argument could leak through recover.

	456 eaexpr(&theSink, n->left);

	457 break;

	458 }

	459

	460 n->trecur = 0;

	461 }

	462

	463

	464

	465 #if 0

	466

	467 for(tl=tstruct->type; tl; tl=tl->down) {

	468 t = tl->type;

	469 if(tl->isddd) {

	470 if(isddd) {

	471 if(nl == nil)

	472 goto notenough;

	473 if(nl->next != nil)

	474 goto toomany;

	475 n = nl->n;

	476 setlineno(n);

	477 if(n->type != T) {

	478 nl->n = assignconv(n, t, desc);

	479 if (call) argused(call, tl, n);

	480 }

	481 goto out;

	482 }

	483 for(; nl; nl=nl->next) {

	484 n = nl->n;

	485 setlineno(nl->n);

	486 if(n->type != T) {

	487 nl->n = assignconv(n, t->type, desc);

	488 if (call) argused(call, tl, n);

	489 }

	490 }

	491 goto out;

	492 }·

	493

	494

	495 // mark that value has been used as the argument arg

	496 static void argused(Node* func, Type* arg, Node* val) {

	497 // if (arg->sym && arg->sym->pkg == localpkg)

	498 // arg->note = strlit("used");

	499 // print("Using %N :: %#T = %N\n", func, arg, val);

	500 }

	501

	502

	503 /*

	504 * type check function definition

	505 */

	506 static void

	507 escanalfunc(Node *n)

	508 {

	509 // Type t, t1, *rcvr;

	510 Type t, rcvr;

	511

	512 typecheck(&n->nname, Erv \| Easgn);

	513 if((t = n->nname->type) == T)

	514 return;

	515 n->type = t;

	516

	517 print("typecheckfunc %T\n", n->type);

	518 for(t1=getinargx(t)->type; t1; t1=t1->down) {

	519 if (isptr[t1->type->etype])

	520 t1->note = strlit("leaks");

	521 print("\t%T\n", t1);

	522

	523 }

	524

	525 rcvr = getthisx(t)->type;

	526 if(rcvr != nil && n->shortname != N && !isblank(n->shortname))

	527 addmethod(n->shortname->sym, t, 1);

	528 }

	529

	530 #endif

OLD	NEW

« no previous file with comments | « src/cmd/gc/Makefile ('k') | src/cmd/gc/gen.c » ('j') | no next file with comments »