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