1// Copyright 2009 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 5package runtime 6 7// This file contains the implementation of Go select statements. 8 9import ( 10 "unsafe" 11) 12 13const debugSelect = false 14 15// scase.kind values. 16// Known to compiler. 17// Changes here must also be made in src/cmd/compile/internal/gc/select.go's walkselectcases. 18const ( 19 caseNil = iota 20 caseRecv 21 caseSend 22 caseDefault 23) 24 25// Select case descriptor. 26// Known to compiler. 27// Changes here must also be made in src/cmd/internal/gc/select.go's scasetype. 28type scase struct { 29 c *hchan // chan 30 elem unsafe.Pointer // data element 31 kind uint16 32 pc uintptr // race pc (for race detector / msan) 33 releasetime int64 34} 35 36var ( 37 chansendpc = funcPC(chansend) 38 chanrecvpc = funcPC(chanrecv) 39) 40 41func selectsetpc(cas *scase) { 42 cas.pc = getcallerpc() 43} 44 45func sellock(scases []scase, lockorder []uint16) { 46 var c *hchan 47 for _, o := range lockorder { 48 c0 := scases[o].c 49 if c0 != nil && c0 != c { 50 c = c0 51 lock(&c.lock) 52 } 53 } 54} 55 56func selunlock(scases []scase, lockorder []uint16) { 57 // We must be very careful here to not touch sel after we have unlocked 58 // the last lock, because sel can be freed right after the last unlock. 59 // Consider the following situation. 60 // First M calls runtime·park() in runtime·selectgo() passing the sel. 61 // Once runtime·park() has unlocked the last lock, another M makes 62 // the G that calls select runnable again and schedules it for execution. 63 // When the G runs on another M, it locks all the locks and frees sel. 64 // Now if the first M touches sel, it will access freed memory. 65 for i := len(scases) - 1; i >= 0; i-- { 66 c := scases[lockorder[i]].c 67 if c == nil { 68 break 69 } 70 if i > 0 && c == scases[lockorder[i-1]].c { 71 continue // will unlock it on the next iteration 72 } 73 unlock(&c.lock) 74 } 75} 76 77func selparkcommit(gp *g, _ unsafe.Pointer) bool { 78 // There are unlocked sudogs that point into gp's stack. Stack 79 // copying must lock the channels of those sudogs. 80 gp.activeStackChans = true 81 // This must not access gp's stack (see gopark). In 82 // particular, it must not access the *hselect. That's okay, 83 // because by the time this is called, gp.waiting has all 84 // channels in lock order. 85 var lastc *hchan 86 for sg := gp.waiting; sg != nil; sg = sg.waitlink { 87 if sg.c != lastc && lastc != nil { 88 // As soon as we unlock the channel, fields in 89 // any sudog with that channel may change, 90 // including c and waitlink. Since multiple 91 // sudogs may have the same channel, we unlock 92 // only after we've passed the last instance 93 // of a channel. 94 unlock(&lastc.lock) 95 } 96 lastc = sg.c 97 } 98 if lastc != nil { 99 unlock(&lastc.lock) 100 } 101 return true 102} 103 104func block() { 105 gopark(nil, nil, waitReasonSelectNoCases, traceEvGoStop, 1) // forever 106} 107 108// selectgo implements the select statement. 109// 110// cas0 points to an array of type [ncases]scase, and order0 points to 111// an array of type [2*ncases]uint16. Both reside on the goroutine's 112// stack (regardless of any escaping in selectgo). 113// 114// selectgo returns the index of the chosen scase, which matches the 115// ordinal position of its respective select{recv,send,default} call. 116// Also, if the chosen scase was a receive operation, it reports whether 117// a value was received. 118func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) { 119 if debugSelect { 120 print("select: cas0=", cas0, "\n") 121 } 122 123 cas1 := (*[1 << 16]scase)(unsafe.Pointer(cas0)) 124 order1 := (*[1 << 17]uint16)(unsafe.Pointer(order0)) 125 126 scases := cas1[:ncases:ncases] 127 pollorder := order1[:ncases:ncases] 128 lockorder := order1[ncases:][:ncases:ncases] 129 130 // Replace send/receive cases involving nil channels with 131 // caseNil so logic below can assume non-nil channel. 132 for i := range scases { 133 cas := &scases[i] 134 if cas.c == nil && cas.kind != caseDefault { 135 *cas = scase{} 136 } 137 } 138 139 var t0 int64 140 if blockprofilerate > 0 { 141 t0 = cputicks() 142 for i := 0; i < ncases; i++ { 143 scases[i].releasetime = -1 144 } 145 } 146 147 // The compiler rewrites selects that statically have 148 // only 0 or 1 cases plus default into simpler constructs. 149 // The only way we can end up with such small sel.ncase 150 // values here is for a larger select in which most channels 151 // have been nilled out. The general code handles those 152 // cases correctly, and they are rare enough not to bother 153 // optimizing (and needing to test). 154 155 // generate permuted order 156 for i := 1; i < ncases; i++ { 157 j := fastrandn(uint32(i + 1)) 158 pollorder[i] = pollorder[j] 159 pollorder[j] = uint16(i) 160 } 161 162 // sort the cases by Hchan address to get the locking order. 163 // simple heap sort, to guarantee n log n time and constant stack footprint. 164 for i := 0; i < ncases; i++ { 165 j := i 166 // Start with the pollorder to permute cases on the same channel. 167 c := scases[pollorder[i]].c 168 for j > 0 && scases[lockorder[(j-1)/2]].c.sortkey() < c.sortkey() { 169 k := (j - 1) / 2 170 lockorder[j] = lockorder[k] 171 j = k 172 } 173 lockorder[j] = pollorder[i] 174 } 175 for i := ncases - 1; i >= 0; i-- { 176 o := lockorder[i] 177 c := scases[o].c 178 lockorder[i] = lockorder[0] 179 j := 0 180 for { 181 k := j*2 + 1 182 if k >= i { 183 break 184 } 185 if k+1 < i && scases[lockorder[k]].c.sortkey() < scases[lockorder[k+1]].c.sortkey() { 186 k++ 187 } 188 if c.sortkey() < scases[lockorder[k]].c.sortkey() { 189 lockorder[j] = lockorder[k] 190 j = k 191 continue 192 } 193 break 194 } 195 lockorder[j] = o 196 } 197 198 if debugSelect { 199 for i := 0; i+1 < ncases; i++ { 200 if scases[lockorder[i]].c.sortkey() > scases[lockorder[i+1]].c.sortkey() { 201 print("i=", i, " x=", lockorder[i], " y=", lockorder[i+1], "\n") 202 throw("select: broken sort") 203 } 204 } 205 } 206 207 // lock all the channels involved in the select 208 sellock(scases, lockorder) 209 210 var ( 211 gp *g 212 sg *sudog 213 c *hchan 214 k *scase 215 sglist *sudog 216 sgnext *sudog 217 qp unsafe.Pointer 218 nextp **sudog 219 ) 220 221loop: 222 // pass 1 - look for something already waiting 223 var dfli int 224 var dfl *scase 225 var casi int 226 var cas *scase 227 var recvOK bool 228 for i := 0; i < ncases; i++ { 229 casi = int(pollorder[i]) 230 cas = &scases[casi] 231 c = cas.c 232 233 switch cas.kind { 234 case caseNil: 235 continue 236 237 case caseRecv: 238 sg = c.sendq.dequeue() 239 if sg != nil { 240 goto recv 241 } 242 if c.qcount > 0 { 243 goto bufrecv 244 } 245 if c.closed != 0 { 246 goto rclose 247 } 248 249 case caseSend: 250 if raceenabled { 251 racereadpc(c.raceaddr(), cas.pc, chansendpc) 252 } 253 if c.closed != 0 { 254 goto sclose 255 } 256 sg = c.recvq.dequeue() 257 if sg != nil { 258 goto send 259 } 260 if c.qcount < c.dataqsiz { 261 goto bufsend 262 } 263 264 case caseDefault: 265 dfli = casi 266 dfl = cas 267 } 268 } 269 270 if dfl != nil { 271 selunlock(scases, lockorder) 272 casi = dfli 273 cas = dfl 274 goto retc 275 } 276 277 // pass 2 - enqueue on all chans 278 gp = getg() 279 if gp.waiting != nil { 280 throw("gp.waiting != nil") 281 } 282 nextp = &gp.waiting 283 for _, casei := range lockorder { 284 casi = int(casei) 285 cas = &scases[casi] 286 if cas.kind == caseNil { 287 continue 288 } 289 c = cas.c 290 sg := acquireSudog() 291 sg.g = gp 292 sg.isSelect = true 293 // No stack splits between assigning elem and enqueuing 294 // sg on gp.waiting where copystack can find it. 295 sg.elem = cas.elem 296 sg.releasetime = 0 297 if t0 != 0 { 298 sg.releasetime = -1 299 } 300 sg.c = c 301 // Construct waiting list in lock order. 302 *nextp = sg 303 nextp = &sg.waitlink 304 305 switch cas.kind { 306 case caseRecv: 307 c.recvq.enqueue(sg) 308 309 case caseSend: 310 c.sendq.enqueue(sg) 311 } 312 } 313 314 // wait for someone to wake us up 315 gp.param = nil 316 gopark(selparkcommit, nil, waitReasonSelect, traceEvGoBlockSelect, 1) 317 gp.activeStackChans = false 318 319 sellock(scases, lockorder) 320 321 gp.selectDone = 0 322 sg = (*sudog)(gp.param) 323 gp.param = nil 324 325 // pass 3 - dequeue from unsuccessful chans 326 // otherwise they stack up on quiet channels 327 // record the successful case, if any. 328 // We singly-linked up the SudoGs in lock order. 329 casi = -1 330 cas = nil 331 sglist = gp.waiting 332 // Clear all elem before unlinking from gp.waiting. 333 for sg1 := gp.waiting; sg1 != nil; sg1 = sg1.waitlink { 334 sg1.isSelect = false 335 sg1.elem = nil 336 sg1.c = nil 337 } 338 gp.waiting = nil 339 340 for _, casei := range lockorder { 341 k = &scases[casei] 342 if k.kind == caseNil { 343 continue 344 } 345 if sglist.releasetime > 0 { 346 k.releasetime = sglist.releasetime 347 } 348 if sg == sglist { 349 // sg has already been dequeued by the G that woke us up. 350 casi = int(casei) 351 cas = k 352 } else { 353 c = k.c 354 if k.kind == caseSend { 355 c.sendq.dequeueSudoG(sglist) 356 } else { 357 c.recvq.dequeueSudoG(sglist) 358 } 359 } 360 sgnext = sglist.waitlink 361 sglist.waitlink = nil 362 releaseSudog(sglist) 363 sglist = sgnext 364 } 365 366 if cas == nil { 367 // We can wake up with gp.param == nil (so cas == nil) 368 // when a channel involved in the select has been closed. 369 // It is easiest to loop and re-run the operation; 370 // we'll see that it's now closed. 371 // Maybe some day we can signal the close explicitly, 372 // but we'd have to distinguish close-on-reader from close-on-writer. 373 // It's easiest not to duplicate the code and just recheck above. 374 // We know that something closed, and things never un-close, 375 // so we won't block again. 376 goto loop 377 } 378 379 c = cas.c 380 381 if debugSelect { 382 print("wait-return: cas0=", cas0, " c=", c, " cas=", cas, " kind=", cas.kind, "\n") 383 } 384 385 if cas.kind == caseRecv { 386 recvOK = true 387 } 388 389 if raceenabled { 390 if cas.kind == caseRecv && cas.elem != nil { 391 raceWriteObjectPC(c.elemtype, cas.elem, cas.pc, chanrecvpc) 392 } else if cas.kind == caseSend { 393 raceReadObjectPC(c.elemtype, cas.elem, cas.pc, chansendpc) 394 } 395 } 396 if msanenabled { 397 if cas.kind == caseRecv && cas.elem != nil { 398 msanwrite(cas.elem, c.elemtype.size) 399 } else if cas.kind == caseSend { 400 msanread(cas.elem, c.elemtype.size) 401 } 402 } 403 404 selunlock(scases, lockorder) 405 goto retc 406 407bufrecv: 408 // can receive from buffer 409 if raceenabled { 410 if cas.elem != nil { 411 raceWriteObjectPC(c.elemtype, cas.elem, cas.pc, chanrecvpc) 412 } 413 raceacquire(chanbuf(c, c.recvx)) 414 racerelease(chanbuf(c, c.recvx)) 415 } 416 if msanenabled && cas.elem != nil { 417 msanwrite(cas.elem, c.elemtype.size) 418 } 419 recvOK = true 420 qp = chanbuf(c, c.recvx) 421 if cas.elem != nil { 422 typedmemmove(c.elemtype, cas.elem, qp) 423 } 424 typedmemclr(c.elemtype, qp) 425 c.recvx++ 426 if c.recvx == c.dataqsiz { 427 c.recvx = 0 428 } 429 c.qcount-- 430 selunlock(scases, lockorder) 431 goto retc 432 433bufsend: 434 // can send to buffer 435 if raceenabled { 436 raceacquire(chanbuf(c, c.sendx)) 437 racerelease(chanbuf(c, c.sendx)) 438 raceReadObjectPC(c.elemtype, cas.elem, cas.pc, chansendpc) 439 } 440 if msanenabled { 441 msanread(cas.elem, c.elemtype.size) 442 } 443 typedmemmove(c.elemtype, chanbuf(c, c.sendx), cas.elem) 444 c.sendx++ 445 if c.sendx == c.dataqsiz { 446 c.sendx = 0 447 } 448 c.qcount++ 449 selunlock(scases, lockorder) 450 goto retc 451 452recv: 453 // can receive from sleeping sender (sg) 454 recv(c, sg, cas.elem, func() { selunlock(scases, lockorder) }, 2) 455 if debugSelect { 456 print("syncrecv: cas0=", cas0, " c=", c, "\n") 457 } 458 recvOK = true 459 goto retc 460 461rclose: 462 // read at end of closed channel 463 selunlock(scases, lockorder) 464 recvOK = false 465 if cas.elem != nil { 466 typedmemclr(c.elemtype, cas.elem) 467 } 468 if raceenabled { 469 raceacquire(c.raceaddr()) 470 } 471 goto retc 472 473send: 474 // can send to a sleeping receiver (sg) 475 if raceenabled { 476 raceReadObjectPC(c.elemtype, cas.elem, cas.pc, chansendpc) 477 } 478 if msanenabled { 479 msanread(cas.elem, c.elemtype.size) 480 } 481 send(c, sg, cas.elem, func() { selunlock(scases, lockorder) }, 2) 482 if debugSelect { 483 print("syncsend: cas0=", cas0, " c=", c, "\n") 484 } 485 goto retc 486 487retc: 488 if cas.releasetime > 0 { 489 blockevent(cas.releasetime-t0, 1) 490 } 491 return casi, recvOK 492 493sclose: 494 // send on closed channel 495 selunlock(scases, lockorder) 496 panic(plainError("send on closed channel")) 497} 498 499func (c *hchan) sortkey() uintptr { 500 return uintptr(unsafe.Pointer(c)) 501} 502 503// A runtimeSelect is a single case passed to rselect. 504// This must match ../reflect/value.go:/runtimeSelect 505type runtimeSelect struct { 506 dir selectDir 507 typ unsafe.Pointer // channel type (not used here) 508 ch *hchan // channel 509 val unsafe.Pointer // ptr to data (SendDir) or ptr to receive buffer (RecvDir) 510} 511 512// These values must match ../reflect/value.go:/SelectDir. 513type selectDir int 514 515const ( 516 _ selectDir = iota 517 selectSend // case Chan <- Send 518 selectRecv // case <-Chan: 519 selectDefault // default 520) 521 522//go:linkname reflect_rselect reflect.rselect 523func reflect_rselect(cases []runtimeSelect) (int, bool) { 524 if len(cases) == 0 { 525 block() 526 } 527 sel := make([]scase, len(cases)) 528 order := make([]uint16, 2*len(cases)) 529 for i := range cases { 530 rc := &cases[i] 531 switch rc.dir { 532 case selectDefault: 533 sel[i] = scase{kind: caseDefault} 534 case selectSend: 535 sel[i] = scase{kind: caseSend, c: rc.ch, elem: rc.val} 536 case selectRecv: 537 sel[i] = scase{kind: caseRecv, c: rc.ch, elem: rc.val} 538 } 539 if raceenabled || msanenabled { 540 selectsetpc(&sel[i]) 541 } 542 } 543 544 return selectgo(&sel[0], &order[0], len(cases)) 545} 546 547func (q *waitq) dequeueSudoG(sgp *sudog) { 548 x := sgp.prev 549 y := sgp.next 550 if x != nil { 551 if y != nil { 552 // middle of queue 553 x.next = y 554 y.prev = x 555 sgp.next = nil 556 sgp.prev = nil 557 return 558 } 559 // end of queue 560 x.next = nil 561 q.last = x 562 sgp.prev = nil 563 return 564 } 565 if y != nil { 566 // start of queue 567 y.prev = nil 568 q.first = y 569 sgp.next = nil 570 return 571 } 572 573 // x==y==nil. Either sgp is the only element in the queue, 574 // or it has already been removed. Use q.first to disambiguate. 575 if q.first == sgp { 576 q.first = nil 577 q.last = nil 578 } 579} 580