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
21 // Select case descriptor.
23 // Changes here must also be made in src/cmd/compile/internal/walk/select.go's scasetype.
26 elem unsafe
.Pointer
// data element
29 func sellock(scases
[]scase
, lockorder
[]uint16) {
31 for _
, o
:= range lockorder
{
40 func selunlock(scases
[]scase
, lockorder
[]uint16) {
41 // We must be very careful here to not touch sel after we have unlocked
42 // the last lock, because sel can be freed right after the last unlock.
43 // Consider the following situation.
44 // First M calls runtime·park() in runtime·selectgo() passing the sel.
45 // Once runtime·park() has unlocked the last lock, another M makes
46 // the G that calls select runnable again and schedules it for execution.
47 // When the G runs on another M, it locks all the locks and frees sel.
48 // Now if the first M touches sel, it will access freed memory.
49 for i
:= len(lockorder
) - 1; i
>= 0; i
-- {
50 c
:= scases
[lockorder
[i
]].c
51 if i
> 0 && c
== scases
[lockorder
[i
-1]].c
{
52 continue // will unlock it on the next iteration
58 func selparkcommit(gp
*g
, _ unsafe
.Pointer
) bool {
59 // There are unlocked sudogs that point into gp's stack. Stack
60 // copying must lock the channels of those sudogs.
61 // Set activeStackChans here instead of before we try parking
62 // because we could self-deadlock in stack growth on a
64 gp
.activeStackChans
= true
65 // Mark that it's safe for stack shrinking to occur now,
66 // because any thread acquiring this G's stack for shrinking
67 // is guaranteed to observe activeStackChans after this store.
68 atomic
.Store8(&gp
.parkingOnChan
, 0)
69 // Make sure we unlock after setting activeStackChans and
70 // unsetting parkingOnChan. The moment we unlock any of the
71 // channel locks we risk gp getting readied by a channel operation
72 // and so gp could continue running before everything before the
73 // unlock is visible (even to gp itself).
75 // This must not access gp's stack (see gopark). In
76 // particular, it must not access the *hselect. That's okay,
77 // because by the time this is called, gp.waiting has all
78 // channels in lock order.
80 for sg
:= gp
.waiting
; sg
!= nil; sg
= sg
.waitlink
{
81 if sg
.c
!= lastc
&& lastc
!= nil {
82 // As soon as we unlock the channel, fields in
83 // any sudog with that channel may change,
84 // including c and waitlink. Since multiple
85 // sudogs may have the same channel, we unlock
86 // only after we've passed the last instance
99 gopark(nil, nil, waitReasonSelectNoCases
, traceEvGoStop
, 1) // forever
102 // selectgo implements the select statement.
104 // cas0 points to an array of type [ncases]scase, and order0 points to
105 // an array of type [2*ncases]uint16 where ncases must be <= 65536.
106 // Both reside on the goroutine's stack (regardless of any escaping in
109 // For race detector builds, pc0 points to an array of type
110 // [ncases]uintptr (also on the stack); for other builds, it's set to
113 // selectgo returns the index of the chosen scase, which matches the
114 // ordinal position of its respective select{recv,send,default} call.
115 // Also, if the chosen scase was a receive operation, it reports whether
116 // a value was received.
117 func selectgo(cas0
*scase
, order0
*uint16, nsends
, nrecvs
int, block
bool) (int, bool) {
119 print("select: cas0=", cas0
, "\n")
122 // NOTE: In order to maintain a lean stack size, the number of scases
123 // is capped at 65536.
124 cas1
:= (*[1 << 16]scase
)(unsafe
.Pointer(cas0
))
125 order1
:= (*[1 << 17]uint16)(unsafe
.Pointer(order0
))
127 ncases
:= nsends
+ nrecvs
128 scases
:= cas1
[:ncases
:ncases
]
129 pollorder
:= order1
[:ncases
:ncases
]
130 lockorder
:= order1
[ncases
:][:ncases
:ncases
]
131 // NOTE: pollorder/lockorder's underlying array was not zero-initialized by compiler.
134 if blockprofilerate
> 0 {
138 // The compiler rewrites selects that statically have
139 // only 0 or 1 cases plus default into simpler constructs.
140 // The only way we can end up with such small sel.ncase
141 // values here is for a larger select in which most channels
142 // have been nilled out. The general code handles those
143 // cases correctly, and they are rare enough not to bother
144 // optimizing (and needing to test).
146 // needed for gccgo, which doesn't zero pollorder
151 // generate permuted order
153 for i
:= range scases
{
156 // Omit cases without channels from the poll and lock orders.
158 cas
.elem
= nil // allow GC
162 j
:= fastrandn(uint32(norder
+ 1))
163 pollorder
[norder
] = pollorder
[j
]
164 pollorder
[j
] = uint16(i
)
167 pollorder
= pollorder
[:norder
]
168 lockorder
= lockorder
[:norder
]
170 // sort the cases by Hchan address to get the locking order.
171 // simple heap sort, to guarantee n log n time and constant stack footprint.
172 for i
:= range lockorder
{
174 // Start with the pollorder to permute cases on the same channel.
175 c
:= scases
[pollorder
[i
]].c
176 for j
> 0 && scases
[lockorder
[(j
-1)/2]].c
.sortkey() < c
.sortkey() {
178 lockorder
[j
] = lockorder
[k
]
181 lockorder
[j
] = pollorder
[i
]
183 for i
:= len(lockorder
) - 1; i
>= 0; i
-- {
186 lockorder
[i
] = lockorder
[0]
193 if k
+1 < i
&& scases
[lockorder
[k
]].c
.sortkey() < scases
[lockorder
[k
+1]].c
.sortkey() {
196 if c
.sortkey() < scases
[lockorder
[k
]].c
.sortkey() {
197 lockorder
[j
] = lockorder
[k
]
207 for i
:= 0; i
+1 < len(lockorder
); i
++ {
208 if scases
[lockorder
[i
]].c
.sortkey() > scases
[lockorder
[i
+1]].c
.sortkey() {
209 print("i=", i
, " x=", lockorder
[i
], " y=", lockorder
[i
+1], "\n")
210 throw("select: broken sort")
215 // lock all the channels involved in the select
216 sellock(scases
, lockorder
)
229 // pass 1 - look for something already waiting
233 var caseReleaseTime
int64 = -1
235 for _
, casei
:= range pollorder
{
241 sg
= c
.sendq
.dequeue()
255 sg
= c
.recvq
.dequeue()
259 if c
.qcount
< c
.dataqsiz
{
266 selunlock(scases
, lockorder
)
271 // pass 2 - enqueue on all chans
273 if gp
.waiting
!= nil {
274 throw("gp.waiting != nil")
277 for _
, casei
:= range lockorder
{
284 // No stack splits between assigning elem and enqueuing
285 // sg on gp.waiting where copystack can find it.
292 // Construct waiting list in lock order.
303 // wait for someone to wake us up
305 // Signal to anyone trying to shrink our stack that we're about
306 // to park on a channel. The window between when this G's status
307 // changes and when we set gp.activeStackChans is not safe for
309 atomic
.Store8(&gp
.parkingOnChan
, 1)
310 gopark(selparkcommit
, nil, waitReasonSelect
, traceEvGoBlockSelect
, 1)
311 gp
.activeStackChans
= false
313 sellock(scases
, lockorder
)
316 sg
= (*sudog
)(gp
.param
)
319 // pass 3 - dequeue from unsuccessful chans
320 // otherwise they stack up on quiet channels
321 // record the successful case, if any.
322 // We singly-linked up the SudoGs in lock order.
327 // Clear all elem before unlinking from gp.waiting.
328 for sg1
:= gp
.waiting
; sg1
!= nil; sg1
= sg1
.waitlink
{
335 for _
, casei
:= range lockorder
{
338 // sg has already been dequeued by the G that woke us up.
341 caseSuccess
= sglist
.success
342 if sglist
.releasetime
> 0 {
343 caseReleaseTime
= sglist
.releasetime
347 if int(casei
) < nsends
{
348 c
.sendq
.dequeueSudoG(sglist
)
350 c
.recvq
.dequeueSudoG(sglist
)
353 sgnext
= sglist
.waitlink
354 sglist
.waitlink
= nil
360 throw("selectgo: bad wakeup")
366 print("wait-return: cas0=", cas0
, " c=", c
, " cas=", cas
, " send=", casi
< nsends
, "\n")
377 selunlock(scases
, lockorder
)
381 // can receive from buffer
383 qp
= chanbuf(c
, c
.recvx
)
385 typedmemmove(c
.elemtype
, cas
.elem
, qp
)
387 typedmemclr(c
.elemtype
, qp
)
389 if c
.recvx
== c
.dataqsiz
{
393 selunlock(scases
, lockorder
)
397 // can send to buffer
398 typedmemmove(c
.elemtype
, chanbuf(c
, c
.sendx
), cas
.elem
)
400 if c
.sendx
== c
.dataqsiz
{
404 selunlock(scases
, lockorder
)
408 // can receive from sleeping sender (sg)
409 recv(c
, sg
, cas
.elem
, func() { selunlock(scases
, lockorder
) }, 2)
411 print("syncrecv: cas0=", cas0
, " c=", c
, "\n")
417 // read at end of closed channel
418 selunlock(scases
, lockorder
)
421 typedmemclr(c
.elemtype
, cas
.elem
)
424 raceacquire(c
.raceaddr())
429 // can send to a sleeping receiver (sg)
430 send(c
, sg
, cas
.elem
, func() { selunlock(scases
, lockorder
) }, 2)
432 print("syncsend: cas0=", cas0
, " c=", c
, "\n")
437 if caseReleaseTime
> 0 {
438 blockevent(caseReleaseTime
-t0
, 1)
441 // Check preemption, since unlike gc we don't check on every call.
442 // A test case for this one is BenchmarkPingPongHog in proc_test.go.
443 if block
&& getg().preempt
{
450 // send on closed channel
451 selunlock(scases
, lockorder
)
452 panic(plainError("send on closed channel"))
455 func (c
*hchan
) sortkey() uintptr {
456 return uintptr(unsafe
.Pointer(c
))
459 // A runtimeSelect is a single case passed to rselect.
460 // This must match ../reflect/value.go:/runtimeSelect
461 type runtimeSelect
struct {
463 typ unsafe
.Pointer
// channel type (not used here)
465 val unsafe
.Pointer
// ptr to data (SendDir) or ptr to receive buffer (RecvDir)
468 // These values must match ../reflect/value.go:/SelectDir.
473 selectSend
// case Chan <- Send
474 selectRecv
// case <-Chan:
475 selectDefault
// default
478 //go:linkname reflect_rselect reflect.rselect
479 func reflect_rselect(cases
[]runtimeSelect
) (int, bool) {
483 sel
:= make([]scase
, len(cases
))
484 orig
:= make([]int, len(cases
))
485 nsends
, nrecvs
:= 0, 0
487 for i
, rc
:= range cases
{
498 j
= len(cases
) - nrecvs
501 sel
[j
] = scase
{c
: rc
.ch
, elem
: rc
.val
}
505 // Only a default case.
506 if nsends
+nrecvs
== 0 {
510 // Compact sel and orig if necessary.
511 if nsends
+nrecvs
< len(cases
) {
512 copy(sel
[nsends
:], sel
[len(cases
)-nrecvs
:])
513 copy(orig
[nsends
:], orig
[len(cases
)-nrecvs
:])
516 order
:= make([]uint16, 2*(nsends
+nrecvs
))
518 chosen
, recvOK
:= selectgo(&sel
[0], &order
[0], nsends
, nrecvs
, dflt
== -1)
520 // Translate chosen back to caller's ordering.
524 chosen
= orig
[chosen
]
526 return chosen
, recvOK
529 func (q
*waitq
) dequeueSudoG(sgp
*sudog
) {
555 // x==y==nil. Either sgp is the only element in the queue,
556 // or it has already been removed. Use q.first to disambiguate.