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