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.
7 // This file contains the implementation of Go select statements.
10 "runtime/internal/atomic"
14 // For gccgo, use go:linkname to export compiler-called functions.
16 //go:linkname selectgo
19 const debugSelect = false
23 // Changes here must also be made in src/cmd/compile/internal/gc/select.go's walkselectcases.
31 // Select case descriptor.
33 // Changes here must also be made in src/cmd/internal/gc/select.go's scasetype.
36 elem unsafe.Pointer // data element
40 func sellock(scases []scase, lockorder []uint16) {
42 for _, o := range lockorder {
51 func selunlock(scases []scase, lockorder []uint16) {
52 // We must be very careful here to not touch sel after we have unlocked
53 // the last lock, because sel can be freed right after the last unlock.
54 // Consider the following situation.
55 // First M calls runtime·park() in runtime·selectgo() passing the sel.
56 // Once runtime·park() has unlocked the last lock, another M makes
57 // the G that calls select runnable again and schedules it for execution.
58 // When the G runs on another M, it locks all the locks and frees sel.
59 // Now if the first M touches sel, it will access freed memory.
60 for i := len(lockorder) - 1; i >= 0; i-- {
61 c := scases[lockorder[i]].c
62 if i > 0 && c == scases[lockorder[i-1]].c {
63 continue // will unlock it on the next iteration
69 func selparkcommit(gp *g, _ unsafe.Pointer) bool {
70 // There are unlocked sudogs that point into gp's stack. Stack
71 // copying must lock the channels of those sudogs.
72 // Set activeStackChans here instead of before we try parking
73 // because we could self-deadlock in stack growth on a
75 gp.activeStackChans = true
76 // Mark that it's safe for stack shrinking to occur now,
77 // because any thread acquiring this G's stack for shrinking
78 // is guaranteed to observe activeStackChans after this store.
79 atomic.Store8(&gp.parkingOnChan, 0)
80 // Make sure we unlock after setting activeStackChans and
81 // unsetting parkingOnChan. The moment we unlock any of the
82 // channel locks we risk gp getting readied by a channel operation
83 // and so gp could continue running before everything before the
84 // unlock is visible (even to gp itself).
86 // This must not access gp's stack (see gopark). In
87 // particular, it must not access the *hselect. That's okay,
88 // because by the time this is called, gp.waiting has all
89 // channels in lock order.
91 for sg := gp.waiting; sg != nil; sg = sg.waitlink {
92 if sg.c != lastc && lastc != nil {
93 // As soon as we unlock the channel, fields in
94 // any sudog with that channel may change,
95 // including c and waitlink. Since multiple
96 // sudogs may have the same channel, we unlock
97 // only after we've passed the last instance
110 gopark(nil, nil, waitReasonSelectNoCases, traceEvGoStop, 1) // forever
113 // selectgo implements the select statement.
115 // cas0 points to an array of type [ncases]scase, and order0 points to
116 // an array of type [2*ncases]uint16 where ncases must be <= 65536.
117 // Both reside on the goroutine's stack (regardless of any escaping in
120 // selectgo returns the index of the chosen scase, which matches the
121 // ordinal position of its respective select{recv,send,default} call.
122 // Also, if the chosen scase was a receive operation, it reports whether
123 // a value was received.
124 func selectgo(cas0 *scase, order0 *uint16, ncases int) (int, bool) {
126 print("select: cas0=", cas0, "\n")
129 // NOTE: In order to maintain a lean stack size, the number of scases
130 // is capped at 65536.
131 cas1 := (*[1 << 16]scase)(unsafe.Pointer(cas0))
132 order1 := (*[1 << 17]uint16)(unsafe.Pointer(order0))
134 scases := cas1[:ncases:ncases]
135 pollorder := order1[:ncases:ncases]
136 lockorder := order1[ncases:][:ncases:ncases]
139 if blockprofilerate > 0 {
143 // The compiler rewrites selects that statically have
144 // only 0 or 1 cases plus default into simpler constructs.
145 // The only way we can end up with such small sel.ncase
146 // values here is for a larger select in which most channels
147 // have been nilled out. The general code handles those
148 // cases correctly, and they are rare enough not to bother
149 // optimizing (and needing to test).
151 // needed for gccgo, which doesn't zero pollorder
156 // generate permuted order
159 for i := range scases {
162 // Omit cases without channels from the poll and lock orders.
164 if cas.kind == caseDefault {
167 cas.elem = nil // allow GC
171 j := fastrandn(uint32(norder + 1))
172 pollorder[norder] = pollorder[j]
173 pollorder[j] = uint16(i)
176 pollorder = pollorder[:norder]
177 lockorder = lockorder[:norder]
179 // sort the cases by Hchan address to get the locking order.
180 // simple heap sort, to guarantee n log n time and constant stack footprint.
181 for i := range lockorder {
183 // Start with the pollorder to permute cases on the same channel.
184 c := scases[pollorder[i]].c
185 for j > 0 && scases[lockorder[(j-1)/2]].c.sortkey() < c.sortkey() {
187 lockorder[j] = lockorder[k]
190 lockorder[j] = pollorder[i]
192 for i := len(lockorder) - 1; i >= 0; i-- {
195 lockorder[i] = lockorder[0]
202 if k+1 < i && scases[lockorder[k]].c.sortkey() < scases[lockorder[k+1]].c.sortkey() {
205 if c.sortkey() < scases[lockorder[k]].c.sortkey() {
206 lockorder[j] = lockorder[k]
216 for i := 0; i+1 < len(lockorder); i++ {
217 if scases[lockorder[i]].c.sortkey() > scases[lockorder[i+1]].c.sortkey() {
218 print("i=", i, " x=", lockorder[i], " y=", lockorder[i+1], "\n")
219 throw("select: broken sort")
224 // lock all the channels involved in the select
225 sellock(scases, lockorder)
239 // pass 1 - look for something already waiting
242 var caseReleaseTime int64 = -1
244 for _, casei := range pollorder {
251 sg = c.sendq.dequeue()
266 sg = c.recvq.dequeue()
270 if c.qcount < c.dataqsiz {
277 selunlock(scases, lockorder)
282 // pass 2 - enqueue on all chans
284 if gp.waiting != nil {
285 throw("gp.waiting != nil")
288 for _, casei := range lockorder {
295 // No stack splits between assigning elem and enqueuing
296 // sg on gp.waiting where copystack can find it.
303 // Construct waiting list in lock order.
316 // wait for someone to wake us up
318 // Signal to anyone trying to shrink our stack that we're about
319 // to park on a channel. The window between when this G's status
320 // changes and when we set gp.activeStackChans is not safe for
322 atomic.Store8(&gp.parkingOnChan, 1)
323 gopark(selparkcommit, nil, waitReasonSelect, traceEvGoBlockSelect, 1)
324 gp.activeStackChans = false
326 sellock(scases, lockorder)
329 sg = (*sudog)(gp.param)
332 // pass 3 - dequeue from unsuccessful chans
333 // otherwise they stack up on quiet channels
334 // record the successful case, if any.
335 // We singly-linked up the SudoGs in lock order.
339 // Clear all elem before unlinking from gp.waiting.
340 for sg1 := gp.waiting; sg1 != nil; sg1 = sg1.waitlink {
347 for _, casei := range lockorder {
350 // sg has already been dequeued by the G that woke us up.
353 if sglist.releasetime > 0 {
354 caseReleaseTime = sglist.releasetime
358 if k.kind == caseSend {
359 c.sendq.dequeueSudoG(sglist)
361 c.recvq.dequeueSudoG(sglist)
364 sgnext = sglist.waitlink
365 sglist.waitlink = nil
371 // We can wake up with gp.param == nil (so cas == nil)
372 // when a channel involved in the select has been closed.
373 // It is easiest to loop and re-run the operation;
374 // we'll see that it's now closed.
375 // Maybe some day we can signal the close explicitly,
376 // but we'd have to distinguish close-on-reader from close-on-writer.
377 // It's easiest not to duplicate the code and just recheck above.
378 // We know that something closed, and things never un-close,
379 // so we won't block again.
386 print("wait-return: cas0=", cas0, " c=", c, " cas=", cas, " kind=", cas.kind, "\n")
389 if cas.kind == caseRecv {
393 selunlock(scases, lockorder)
397 // can receive from buffer
399 qp = chanbuf(c, c.recvx)
401 typedmemmove(c.elemtype, cas.elem, qp)
403 typedmemclr(c.elemtype, qp)
405 if c.recvx == c.dataqsiz {
409 selunlock(scases, lockorder)
413 // can send to buffer
414 typedmemmove(c.elemtype, chanbuf(c, c.sendx), cas.elem)
416 if c.sendx == c.dataqsiz {
420 selunlock(scases, lockorder)
424 // can receive from sleeping sender (sg)
425 recv(c, sg, cas.elem, func() { selunlock(scases, lockorder) }, 2)
427 print("syncrecv: cas0=", cas0, " c=", c, "\n")
433 // read at end of closed channel
434 selunlock(scases, lockorder)
437 typedmemclr(c.elemtype, cas.elem)
440 raceacquire(c.raceaddr())
445 // can send to a sleeping receiver (sg)
446 send(c, sg, cas.elem, func() { selunlock(scases, lockorder) }, 2)
448 print("syncsend: cas0=", cas0, " c=", c, "\n")
453 if caseReleaseTime > 0 {
454 blockevent(caseReleaseTime-t0, 1)
457 // Check preemption, since unlike gc we don't check on every call.
458 // A test case for this one is BenchmarkPingPongHog in proc_test.go.
459 if dfli >= 0 && getg().preempt {
466 // send on closed channel
467 selunlock(scases, lockorder)
468 panic(plainError("send on closed channel"))
471 func (c *hchan) sortkey() uintptr {
472 return uintptr(unsafe.Pointer(c))
475 // A runtimeSelect is a single case passed to rselect.
476 // This must match ../reflect/value.go:/runtimeSelect
477 type runtimeSelect struct {
479 typ unsafe.Pointer // channel type (not used here)
481 val unsafe.Pointer // ptr to data (SendDir) or ptr to receive buffer (RecvDir)
484 // These values must match ../reflect/value.go:/SelectDir.
489 selectSend // case Chan <- Send
490 selectRecv // case <-Chan:
491 selectDefault // default
494 //go:linkname reflect_rselect reflect.rselect
495 func reflect_rselect(cases []runtimeSelect) (int, bool) {
499 sel := make([]scase, len(cases))
500 order := make([]uint16, 2*len(cases))
501 for i := range cases {
505 sel[i] = scase{kind: caseDefault}
507 sel[i] = scase{kind: caseSend, c: rc.ch, elem: rc.val}
509 sel[i] = scase{kind: caseRecv, c: rc.ch, elem: rc.val}
513 return selectgo(&sel[0], &order[0], len(cases))
516 func (q *waitq) dequeueSudoG(sgp *sudog) {
542 // x==y==nil. Either sgp is the only element in the queue,
543 // or it has already been removed. Use q.first to disambiguate.