src/cmd/compile/internal/gc/racewalk.go

   1 // Copyright 2012 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package gc
   6
   7 import (
   8         "fmt"
   9         "strings"
  10 )
  11
  12 // The racewalk pass modifies the code tree for the function as follows:
  13 //
  14 // 1. It inserts a call to racefuncenterfp at the beginning of each function.
  15 // 2. It inserts a call to racefuncexit at the end of each function.
  16 // 3. It inserts a call to raceread before each memory read.
  17 // 4. It inserts a call to racewrite before each memory write.
  18 //
  19 // The rewriting is not yet complete. Certain nodes are not rewritten
  20 // but should be.
  21
  22 // TODO(dvyukov): do not instrument initialization as writes:
  23 // a := make([]int, 10)
  24
  25 // Do not instrument the following packages at all,
  26 // at best instrumentation would cause infinite recursion.
  27 var omit_pkgs = []string{"runtime", "runtime/race"}
  28
  29 // Only insert racefuncenterfp/racefuncexit into the following packages.
  30 // Memory accesses in the packages are either uninteresting or will cause false positives.
  31 var noinst_pkgs = []string{"sync", "sync/atomic"}
  32
  33 func ispkgin(pkgs []string) bool {
  34         if myimportpath != "" {
  35                 for _, p := range pkgs {
  36                         if myimportpath == p {
  37                                 return true
  38                         }
  39                 }
  40         }
  41
  42         return false
  43 }
  44
  45 // TODO(rsc): Remove. Put //go:norace on forkAndExecInChild instead.
  46 func isforkfunc(fn *Node) bool {
  47         // Special case for syscall.forkAndExecInChild.
  48         // In the child, this function must not acquire any locks, because
  49         // they might have been locked at the time of the fork.  This means
  50         // no rescheduling, no malloc calls, and no new stack segments.
  51         // Race instrumentation does all of the above.
  52         return myimportpath != "" && myimportpath == "syscall" && fn.Func.Nname.Sym.Name == "forkAndExecInChild"
  53 }
  54
  55 func racewalk(fn *Node) {
  56         if ispkgin(omit_pkgs) || isforkfunc(fn) || fn.Func.Norace {
  57                 return
  58         }
  59
  60         if !ispkgin(noinst_pkgs) {
  61                 racewalklist(fn.Nbody, nil)
  62
  63                 // nothing interesting for race detector in fn->enter
  64                 racewalklist(fn.Func.Exit, nil)
  65         }
  66
  67         nd := mkcall("racefuncenterfp", nil, nil, Nod(OADDR, nodfp, nil))
  68         fn.Func.Enter = concat(list1(nd), fn.Func.Enter)
  69         nd = mkcall("racefuncexit", nil, nil)
  70         fn.Func.Exit = list(fn.Func.Exit, nd)
  71
  72         if Debug['W'] != 0 {
  73                 s := fmt.Sprintf("after racewalk %v", fn.Func.Nname.Sym)
  74                 dumplist(s, fn.Nbody)
  75                 s = fmt.Sprintf("enter %v", fn.Func.Nname.Sym)
  76                 dumplist(s, fn.Func.Enter)
  77                 s = fmt.Sprintf("exit %v", fn.Func.Nname.Sym)
  78                 dumplist(s, fn.Func.Exit)
  79         }
  80 }
  81
  82 func racewalklist(l *NodeList, init **NodeList) {
  83         var instr *NodeList
  84
  85         for ; l != nil; l = l.Next {
  86                 instr = nil
  87                 racewalknode(&l.N, &instr, 0, 0)
  88                 if init == nil {
  89                         l.N.Ninit = concat(l.N.Ninit, instr)
  90                 } else {
  91                         *init = concat(*init, instr)
  92                 }
  93         }
  94 }
  95
  96 // walkexpr and walkstmt combined
  97 // walks the tree and adds calls to the
  98 // instrumentation code to top-level (statement) nodes' init
  99 func racewalknode(np **Node, init **NodeList, wr int, skip int) {
 100         n := *np
 101
 102         if n == nil {
 103                 return
 104         }
 105
 106         if Debug['w'] > 1 {
 107                 Dump("racewalk-before", n)
 108         }
 109         setlineno(n)
 110         if init == nil {
 111                 Fatalf("racewalk: bad init list")
 112         }
 113         if init == &n.Ninit {
 114                 // If init == &n->ninit and n->ninit is non-nil,
 115                 // racewalknode might append it to itself.
 116                 // nil it out and handle it separately before putting it back.
 117                 l := n.Ninit
 118
 119                 n.Ninit = nil
 120                 racewalklist(l, nil)
 121                 racewalknode(&n, &l, wr, skip) // recurse with nil n->ninit
 122                 appendinit(&n, l)
 123                 *np = n
 124                 return
 125         }
 126
 127         racewalklist(n.Ninit, nil)
 128
 129         switch n.Op {
 130         default:
 131                 Fatalf("racewalk: unknown node type %v", Oconv(int(n.Op), 0))
 132
 133         case OAS, OASWB, OAS2FUNC:
 134                 racewalknode(&n.Left, init, 1, 0)
 135                 racewalknode(&n.Right, init, 0, 0)
 136                 goto ret
 137
 138                 // can't matter
 139         case OCFUNC, OVARKILL:
 140                 goto ret
 141
 142         case OBLOCK:
 143                 var out *NodeList
 144                 for l := n.List; l != nil; l = l.Next {
 145                         switch l.N.Op {
 146                         case OCALLFUNC, OCALLMETH, OCALLINTER:
 147                                 racewalknode(&l.N, &out, 0, 0)
 148                                 out = list(out, l.N)
 149                                 // Scan past OAS nodes copying results off stack.
 150                                 // Those must not be instrumented, because the
 151                                 // instrumentation calls will smash the results.
 152                                 // The assignments are to temporaries, so they cannot
 153                                 // be involved in races and need not be instrumented.
 154                                 for l.Next != nil && l.Next.N.Op == OAS && iscallret(l.Next.N.Right) {
 155                                         l = l.Next
 156                                         out = list(out, l.N)
 157                                 }
 158                         default:
 159                                 racewalknode(&l.N, &out, 0, 0)
 160                                 out = list(out, l.N)
 161                         }
 162                 }
 163                 n.List = out
 164                 goto ret
 165
 166         case ODEFER:
 167                 racewalknode(&n.Left, init, 0, 0)
 168                 goto ret
 169
 170         case OPROC:
 171                 racewalknode(&n.Left, init, 0, 0)
 172                 goto ret
 173
 174         case OCALLINTER:
 175                 racewalknode(&n.Left, init, 0, 0)
 176                 goto ret
 177
 178                 // Instrument dst argument of runtime.writebarrier* calls
 179         // as we do not instrument runtime code.
 180         // typedslicecopy is instrumented in runtime.
 181         case OCALLFUNC:
 182                 racewalknode(&n.Left, init, 0, 0)
 183                 goto ret
 184
 185         case ONOT,
 186                 OMINUS,
 187                 OPLUS,
 188                 OREAL,
 189                 OIMAG,
 190                 OCOM,
 191                 OSQRT:
 192                 racewalknode(&n.Left, init, wr, 0)
 193                 goto ret
 194
 195         case ODOTINTER:
 196                 racewalknode(&n.Left, init, 0, 0)
 197                 goto ret
 198
 199         case ODOT:
 200                 racewalknode(&n.Left, init, 0, 1)
 201                 callinstr(&n, init, wr, skip)
 202                 goto ret
 203
 204         case ODOTPTR: // dst = (*x).f with implicit *; otherwise it's ODOT+OIND
 205                 racewalknode(&n.Left, init, 0, 0)
 206
 207                 callinstr(&n, init, wr, skip)
 208                 goto ret
 209
 210         case OIND: // *p
 211                 racewalknode(&n.Left, init, 0, 0)
 212
 213                 callinstr(&n, init, wr, skip)
 214                 goto ret
 215
 216         case OSPTR, OLEN, OCAP:
 217                 racewalknode(&n.Left, init, 0, 0)
 218                 if Istype(n.Left.Type, TMAP) {
 219                         n1 := Nod(OCONVNOP, n.Left, nil)
 220                         n1.Type = Ptrto(Types[TUINT8])
 221                         n1 = Nod(OIND, n1, nil)
 222                         typecheck(&n1, Erv)
 223                         callinstr(&n1, init, 0, skip)
 224                 }
 225
 226                 goto ret
 227
 228         case OLSH,
 229                 ORSH,
 230                 OLROT,
 231                 OAND,
 232                 OANDNOT,
 233                 OOR,
 234                 OXOR,
 235                 OSUB,
 236                 OMUL,
 237                 OHMUL,
 238                 OEQ,
 239                 ONE,
 240                 OLT,
 241                 OLE,
 242                 OGE,
 243                 OGT,
 244                 OADD,
 245                 OCOMPLEX:
 246                 racewalknode(&n.Left, init, wr, 0)
 247                 racewalknode(&n.Right, init, wr, 0)
 248                 goto ret
 249
 250         case OANDAND, OOROR:
 251                 racewalknode(&n.Left, init, wr, 0)
 252
 253                 // walk has ensured the node has moved to a location where
 254                 // side effects are safe.
 255                 // n->right may not be executed,
 256                 // so instrumentation goes to n->right->ninit, not init.
 257                 racewalknode(&n.Right, &n.Right.Ninit, wr, 0)
 258
 259                 goto ret
 260
 261         case ONAME:
 262                 callinstr(&n, init, wr, skip)
 263                 goto ret
 264
 265         case OCONV:
 266                 racewalknode(&n.Left, init, wr, 0)
 267                 goto ret
 268
 269         case OCONVNOP:
 270                 racewalknode(&n.Left, init, wr, 0)
 271                 goto ret
 272
 273         case ODIV, OMOD:
 274                 racewalknode(&n.Left, init, wr, 0)
 275                 racewalknode(&n.Right, init, wr, 0)
 276                 goto ret
 277
 278         case OINDEX:
 279                 if !Isfixedarray(n.Left.Type) {
 280                         racewalknode(&n.Left, init, 0, 0)
 281                 } else if !islvalue(n.Left) {
 282                         // index of unaddressable array, like Map[k][i].
 283                         racewalknode(&n.Left, init, wr, 0)
 284
 285                         racewalknode(&n.Right, init, 0, 0)
 286                         goto ret
 287                 }
 288
 289                 racewalknode(&n.Right, init, 0, 0)
 290                 if n.Left.Type.Etype != TSTRING {
 291                         callinstr(&n, init, wr, skip)
 292                 }
 293                 goto ret
 294
 295         case OSLICE, OSLICEARR, OSLICE3, OSLICE3ARR, OSLICESTR:
 296                 racewalknode(&n.Left, init, 0, 0)
 297                 racewalknode(&n.Right, init, 0, 0)
 298                 goto ret
 299
 300         case OKEY:
 301                 racewalknode(&n.Left, init, 0, 0)
 302                 racewalknode(&n.Right, init, 0, 0)
 303                 goto ret
 304
 305         case OADDR:
 306                 racewalknode(&n.Left, init, 0, 1)
 307                 goto ret
 308
 309                 // n->left is Type* which is not interesting.
 310         case OEFACE:
 311                 racewalknode(&n.Right, init, 0, 0)
 312
 313                 goto ret
 314
 315         case OITAB:
 316                 racewalknode(&n.Left, init, 0, 0)
 317                 goto ret
 318
 319                 // should not appear in AST by now
 320         case OSEND,
 321                 ORECV,
 322                 OCLOSE,
 323                 ONEW,
 324                 OXCASE,
 325                 OXFALL,
 326                 OCASE,
 327                 OPANIC,
 328                 ORECOVER,
 329                 OCONVIFACE,
 330                 OCMPIFACE,
 331                 OMAKECHAN,
 332                 OMAKEMAP,
 333                 OMAKESLICE,
 334                 OCALL,
 335                 OCOPY,
 336                 OAPPEND,
 337                 ORUNESTR,
 338                 OARRAYBYTESTR,
 339                 OARRAYRUNESTR,
 340                 OSTRARRAYBYTE,
 341                 OSTRARRAYRUNE,
 342                 OINDEXMAP,
 343                 // lowered to call
 344                 OCMPSTR,
 345                 OADDSTR,
 346                 ODOTTYPE,
 347                 ODOTTYPE2,
 348                 OAS2DOTTYPE,
 349                 OCALLPART,
 350                 // lowered to PTRLIT
 351                 OCLOSURE,  // lowered to PTRLIT
 352                 ORANGE,    // lowered to ordinary for loop
 353                 OARRAYLIT, // lowered to assignments
 354                 OMAPLIT,
 355                 OSTRUCTLIT,
 356                 OAS2,
 357                 OAS2RECV,
 358                 OAS2MAPR,
 359                 OASOP:
 360                 Yyerror("racewalk: %v must be lowered by now", Oconv(int(n.Op), 0))
 361
 362                 goto ret
 363
 364                 // impossible nodes: only appear in backend.
 365         case ORROTC, OEXTEND:
 366                 Yyerror("racewalk: %v cannot exist now", Oconv(int(n.Op), 0))
 367                 goto ret
 368
 369         case OGETG:
 370                 Yyerror("racewalk: OGETG can happen only in runtime which we don't instrument")
 371                 goto ret
 372
 373         case OFOR:
 374                 if n.Left != nil {
 375                         racewalknode(&n.Left, &n.Left.Ninit, 0, 0)
 376                 }
 377                 if n.Right != nil {
 378                         racewalknode(&n.Right, &n.Right.Ninit, 0, 0)
 379                 }
 380                 goto ret
 381
 382         case OIF, OSWITCH:
 383                 if n.Left != nil {
 384                         racewalknode(&n.Left, &n.Left.Ninit, 0, 0)
 385                 }
 386                 goto ret
 387
 388                 // just do generic traversal
 389         case OCALLMETH,
 390                 ORETURN,
 391                 ORETJMP,
 392                 OSELECT,
 393                 OEMPTY,
 394                 OBREAK,
 395                 OCONTINUE,
 396                 OFALL,
 397                 OGOTO,
 398                 OLABEL:
 399                 goto ret
 400
 401                 // does not require instrumentation
 402         case OPRINT, // don't bother instrumenting it
 403                 OPRINTN,     // don't bother instrumenting it
 404                 OCHECKNIL,   // always followed by a read.
 405                 OPARAM,      // it appears only in fn->exit to copy heap params back
 406                 OCLOSUREVAR, // immutable pointer to captured variable
 407                 ODOTMETH,    // either part of CALLMETH or CALLPART (lowered to PTRLIT)
 408                 OINDREG,     // at this stage, only n(SP) nodes from nodarg
 409                 ODCL,        // declarations (without value) cannot be races
 410                 ODCLCONST,
 411                 ODCLTYPE,
 412                 OTYPE,
 413                 ONONAME,
 414                 OLITERAL,
 415                 OTYPESW: // ignored by code generation, do not instrument.
 416                 goto ret
 417         }
 418
 419 ret:
 420         if n.Op != OBLOCK { // OBLOCK is handled above in a special way.
 421                 racewalklist(n.List, init)
 422         }
 423         racewalklist(n.Nbody, nil)
 424         racewalklist(n.Rlist, nil)
 425         *np = n
 426 }
 427
 428 func isartificial(n *Node) bool {
 429         // compiler-emitted artificial things that we do not want to instrument,
 430         // cant' possibly participate in a data race.
 431         if n.Op == ONAME && n.Sym != nil && n.Sym.Name != "" {
 432                 if n.Sym.Name == "_" {
 433                         return true
 434                 }
 435
 436                 // autotmp's are always local
 437                 if strings.HasPrefix(n.Sym.Name, "autotmp_") {
 438                         return true
 439                 }
 440
 441                 // statictmp's are read-only
 442                 if strings.HasPrefix(n.Sym.Name, "statictmp_") {
 443                         return true
 444                 }
 445
 446                 // go.itab is accessed only by the compiler and runtime (assume safe)
 447                 if n.Sym.Pkg != nil && n.Sym.Pkg.Name != "" && n.Sym.Pkg.Name == "go.itab" {
 448                         return true
 449                 }
 450         }
 451
 452         return false
 453 }
 454
 455 func callinstr(np **Node, init **NodeList, wr int, skip int) bool {
 456         n := *np
 457
 458         //print("callinstr for %+N [ %O ] etype=%E class=%d\n",
 459         //        n, n->op, n->type ? n->type->etype : -1, n->class);
 460
 461         if skip != 0 || n.Type == nil || n.Type.Etype >= TIDEAL {
 462                 return false
 463         }
 464         t := n.Type
 465         if isartificial(n) {
 466                 return false
 467         }
 468
 469         b := outervalue(n)
 470
 471         // it skips e.g. stores to ... parameter array
 472         if isartificial(b) {
 473                 return false
 474         }
 475         class := b.Class
 476
 477         // BUG: we _may_ want to instrument PAUTO sometimes
 478         // e.g. if we've got a local variable/method receiver
 479         // that has got a pointer inside. Whether it points to
 480         // the heap or not is impossible to know at compile time
 481         if (class&PHEAP != 0) || class == PPARAMREF || class == PEXTERN || b.Op == OINDEX || b.Op == ODOTPTR || b.Op == OIND {
 482                 hascalls := 0
 483                 foreach(n, hascallspred, &hascalls)
 484                 if hascalls != 0 {
 485                         n = detachexpr(n, init)
 486                         *np = n
 487                 }
 488
 489                 n = treecopy(n, 0)
 490                 makeaddable(n)
 491                 var f *Node
 492                 if t.Etype == TSTRUCT || Isfixedarray(t) {
 493                         name := "racereadrange"
 494                         if wr != 0 {
 495                                 name = "racewriterange"
 496                         }
 497                         f = mkcall(name, nil, init, uintptraddr(n), Nodintconst(t.Width))
 498                 } else {
 499                         name := "raceread"
 500                         if wr != 0 {
 501                                 name = "racewrite"
 502                         }
 503                         f = mkcall(name, nil, init, uintptraddr(n))
 504                 }
 505
 506                 *init = list(*init, f)
 507                 return true
 508         }
 509
 510         return false
 511 }
 512
 513 // makeaddable returns a node whose memory location is the
 514 // same as n, but which is addressable in the Go language
 515 // sense.
 516 // This is different from functions like cheapexpr that may make
 517 // a copy of their argument.
 518 func makeaddable(n *Node) {
 519         // The arguments to uintptraddr technically have an address but
 520         // may not be addressable in the Go sense: for example, in the case
 521         // of T(v).Field where T is a struct type and v is
 522         // an addressable value.
 523         switch n.Op {
 524         case OINDEX:
 525                 if Isfixedarray(n.Left.Type) {
 526                         makeaddable(n.Left)
 527                 }
 528
 529                 // Turn T(v).Field into v.Field
 530         case ODOT, OXDOT:
 531                 if n.Left.Op == OCONVNOP {
 532                         n.Left = n.Left.Left
 533                 }
 534                 makeaddable(n.Left)
 535
 536                 // nothing to do
 537         case ODOTPTR:
 538                 fallthrough
 539         default:
 540                 break
 541         }
 542 }
 543
 544 func uintptraddr(n *Node) *Node {
 545         r := Nod(OADDR, n, nil)
 546         r.Bounded = true
 547         r = conv(r, Types[TUNSAFEPTR])
 548         r = conv(r, Types[TUINTPTR])
 549         return r
 550 }
 551
 552 func detachexpr(n *Node, init **NodeList) *Node {
 553         addr := Nod(OADDR, n, nil)
 554         l := temp(Ptrto(n.Type))
 555         as := Nod(OAS, l, addr)
 556         typecheck(&as, Etop)
 557         walkexpr(&as, init)
 558         *init = list(*init, as)
 559         ind := Nod(OIND, l, nil)
 560         typecheck(&ind, Erv)
 561         walkexpr(&ind, init)
 562         return ind
 563 }
 564
 565 func foreachnode(n *Node, f func(*Node, interface{}), c interface{}) {
 566         if n != nil {
 567                 f(n, c)
 568         }
 569 }
 570
 571 func foreachlist(l *NodeList, f func(*Node, interface{}), c interface{}) {
 572         for ; l != nil; l = l.Next {
 573                 foreachnode(l.N, f, c)
 574         }
 575 }
 576
 577 func foreach(n *Node, f func(*Node, interface{}), c interface{}) {
 578         foreachlist(n.Ninit, f, c)
 579         foreachnode(n.Left, f, c)
 580         foreachnode(n.Right, f, c)
 581         foreachlist(n.List, f, c)
 582         foreachlist(n.Nbody, f, c)
 583         foreachlist(n.Rlist, f, c)
 584 }
 585
 586 func hascallspred(n *Node, c interface{}) {
 587         switch n.Op {
 588         case OCALL, OCALLFUNC, OCALLMETH, OCALLINTER:
 589                 (*c.(*int))++
 590         }
 591 }
 592
 593 // appendinit is like addinit in subr.go
 594 // but appends rather than prepends.
 595 func appendinit(np **Node, init *NodeList) {
 596         if init == nil {
 597                 return
 598         }
 599
 600         n := *np
 601         switch n.Op {
 602         // There may be multiple refs to this node;
 603         // introduce OCONVNOP to hold init list.
 604         case ONAME, OLITERAL:
 605                 n = Nod(OCONVNOP, n, nil)
 606
 607                 n.Type = n.Left.Type
 608                 n.Typecheck = 1
 609                 *np = n
 610         }
 611
 612         n.Ninit = concat(n.Ninit, init)
 613         n.Ullman = UINF
 614 }