1 // Copyright 2014 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 channels.
10 // At least one of c.sendq and c.recvq is empty,
11 // except for the case of an unbuffered channel with a single goroutine
12 // blocked on it for both sending and receiving using a select statement,
13 // in which case the length of c.sendq and c.recvq is limited only by the
14 // size of the select statement.
16 // For buffered channels, also:
17 // c.qcount > 0 implies that c.recvq is empty.
18 // c.qcount < c.dataqsiz implies that c.sendq is empty.
21 "runtime/internal/atomic"
25 // For gccgo, use go:linkname to rename compiler-called functions to
26 // themselves, so that the compiler will export them.
28 //go:linkname makechan runtime.makechan
29 //go:linkname chansend1 runtime.chansend1
30 //go:linkname chanrecv1 runtime.chanrecv1
31 //go:linkname chanrecv2 runtime.chanrecv2
32 //go:linkname closechan runtime.closechan
36 hchanSize
= unsafe
.Sizeof(hchan
{}) + uintptr(-int(unsafe
.Sizeof(hchan
{}))&(maxAlign
-1))
41 qcount
uint // total data in the queue
42 dataqsiz
uint // size of the circular queue
43 buf unsafe
.Pointer
// points to an array of dataqsiz elements
46 elemtype
*_type
// element type
47 sendx
uint // send index
48 recvx
uint // receive index
49 recvq waitq
// list of recv waiters
50 sendq waitq
// list of send waiters
52 // lock protects all fields in hchan, as well as several
53 // fields in sudogs blocked on this channel.
55 // Do not change another G's status while holding this lock
56 // (in particular, do not ready a G), as this can deadlock
57 // with stack shrinking.
66 //go:linkname reflect_makechan reflect.makechan
67 func reflect_makechan(t
*chantype
, size
int64) *hchan
{
68 return makechan(t
, size
)
71 func makechan(t
*chantype
, size
int64) *hchan
{
74 // compiler checks this but be safe.
75 if elem
.size
>= 1<<16 {
76 throw("makechan: invalid channel element type")
78 if hchanSize%maxAlign
!= 0 || elem
.align
> maxAlign
{
79 throw("makechan: bad alignment")
81 if size
< 0 ||
int64(uintptr(size
)) != size ||
(elem
.size
> 0 && uintptr(size
) > (_MaxMem
-hchanSize
)/elem
.size
) {
82 panic(plainError("makechan: size out of range"))
86 if elem
.kind
&kindNoPointers
!= 0 || size
== 0 {
87 // Allocate memory in one call.
88 // Hchan does not contain pointers interesting for GC in this case:
89 // buf points into the same allocation, elemtype is persistent.
90 // SudoG's are referenced from their owning thread so they can't be collected.
91 // TODO(dvyukov,rlh): Rethink when collector can move allocated objects.
92 c
= (*hchan
)(mallocgc(hchanSize
+uintptr(size
)*elem
.size
, nil, true))
93 if size
> 0 && elem
.size
!= 0 {
94 c
.buf
= add(unsafe
.Pointer(c
), hchanSize
)
96 // race detector uses this location for synchronization
97 // Also prevents us from pointing beyond the allocation (see issue 9401).
98 c
.buf
= unsafe
.Pointer(c
)
102 c
.buf
= newarray(elem
, int(size
))
104 c
.elemsize
= uint16(elem
.size
)
106 c
.dataqsiz
= uint(size
)
109 print("makechan: chan=", c
, "; elemsize=", elem
.size
, "; dataqsiz=", size
, "\n")
114 // chanbuf(c, i) is pointer to the i'th slot in the buffer.
115 func chanbuf(c
*hchan
, i
uint) unsafe
.Pointer
{
116 return add(c
.buf
, uintptr(i
)*uintptr(c
.elemsize
))
119 // entry point for c <- x from compiled code
121 func chansend1(t
*chantype
, c
*hchan
, elem unsafe
.Pointer
) {
122 chansend(t
, c
, elem
, true, getcallerpc(unsafe
.Pointer(&t
)))
126 * generic single channel send/recv
127 * If block is not nil,
128 * then the protocol will not
129 * sleep but return if it could
132 * sleep can wake up with g.param == nil
133 * when a channel involved in the sleep has
134 * been closed. it is easiest to loop and re-run
135 * the operation; we'll see that it's now closed.
137 func chansend(t
*chantype
, c
*hchan
, ep unsafe
.Pointer
, block
bool, callerpc
uintptr) bool {
139 raceReadObjectPC(t
.elem
, ep
, callerpc
, funcPC(chansend
))
142 msanread(ep
, t
.elem
.size
)
149 gopark(nil, nil, "chan send (nil chan)", traceEvGoStop
, 2)
154 print("chansend: chan=", c
, "\n")
158 racereadpc(unsafe
.Pointer(c
), callerpc
, funcPC(chansend
))
161 // Fast path: check for failed non-blocking operation without acquiring the lock.
163 // After observing that the channel is not closed, we observe that the channel is
164 // not ready for sending. Each of these observations is a single word-sized read
165 // (first c.closed and second c.recvq.first or c.qcount depending on kind of channel).
166 // Because a closed channel cannot transition from 'ready for sending' to
167 // 'not ready for sending', even if the channel is closed between the two observations,
168 // they imply a moment between the two when the channel was both not yet closed
169 // and not ready for sending. We behave as if we observed the channel at that moment,
170 // and report that the send cannot proceed.
172 // It is okay if the reads are reordered here: if we observe that the channel is not
173 // ready for sending and then observe that it is not closed, that implies that the
174 // channel wasn't closed during the first observation.
175 if !block
&& c
.closed == 0 && ((c
.dataqsiz
== 0 && c
.recvq
.first
== nil) ||
176 (c
.dataqsiz
> 0 && c
.qcount
== c
.dataqsiz
)) {
181 if blockprofilerate
> 0 {
189 panic(plainError("send on closed channel"))
192 if sg
:= c
.recvq
.dequeue(); sg
!= nil {
193 // Found a waiting receiver. We pass the value we want to send
194 // directly to the receiver, bypassing the channel buffer (if any).
195 send(c
, sg
, ep
, func() { unlock(&c
.lock
) })
199 if c
.qcount
< c
.dataqsiz
{
200 // Space is available in the channel buffer. Enqueue the element to send.
201 qp
:= chanbuf(c
, c
.sendx
)
206 typedmemmove(c
.elemtype
, qp
, ep
)
208 if c
.sendx
== c
.dataqsiz
{
221 // Block on the channel. Some receiver will complete our operation for us.
223 mysg
:= acquireSudog()
226 mysg
.releasetime
= -1
228 // No stack splits between assigning elem and enqueuing mysg
229 // on gp.waiting where copystack can find it.
233 mysg
.selectdone
= nil
237 c
.sendq
.enqueue(mysg
)
238 goparkunlock(&c
.lock
, "chan send", traceEvGoBlockSend
, 3)
240 // someone woke us up.
241 if mysg
!= gp
.waiting
{
242 throw("G waiting list is corrupted")
247 throw("chansend: spurious wakeup")
249 panic(plainError("send on closed channel"))
252 if mysg
.releasetime
> 0 {
253 blockevent(mysg
.releasetime
-t0
, 2)
260 // send processes a send operation on an empty channel c.
261 // The value ep sent by the sender is copied to the receiver sg.
262 // The receiver is then woken up to go on its merry way.
263 // Channel c must be empty and locked. send unlocks c with unlockf.
264 // sg must already be dequeued from c.
265 // ep must be non-nil and point to the heap or the caller's stack.
266 func send(c
*hchan
, sg
*sudog
, ep unsafe
.Pointer
, unlockf
func()) {
271 // Pretend we go through the buffer, even though
272 // we copy directly. Note that we need to increment
273 // the head/tail locations only when raceenabled.
274 qp
:= chanbuf(c
, c
.recvx
)
277 raceacquireg(sg
.g
, qp
)
278 racereleaseg(sg
.g
, qp
)
280 if c
.recvx
== c
.dataqsiz
{
283 c
.sendx
= c
.recvx
// c.sendx = (c.sendx+1) % c.dataqsiz
287 sendDirect(c
.elemtype
, sg
, ep
)
292 gp
.param
= unsafe
.Pointer(sg
)
293 if sg
.releasetime
!= 0 {
294 sg
.releasetime
= cputicks()
299 // Sends and receives on unbuffered or empty-buffered channels are the
300 // only operations where one running goroutine writes to the stack of
301 // another running goroutine. The GC assumes that stack writes only
302 // happen when the goroutine is running and are only done by that
303 // goroutine. Using a write barrier is sufficient to make up for
304 // violating that assumption, but the write barrier has to work.
305 // typedmemmove will call bulkBarrierPreWrite, but the target bytes
306 // are not in the heap, so that will not help. We arrange to call
307 // memmove and typeBitsBulkBarrier instead.
309 func sendDirect(t
*_type
, sg
*sudog
, src unsafe
.Pointer
) {
310 // src is on our stack, dst is a slot on another stack.
312 // Once we read sg.elem out of sg, it will no longer
313 // be updated if the destination's stack gets copied (shrunk).
314 // So make sure that no preemption points can happen between read & use.
316 typeBitsBulkBarrier(t
, uintptr(dst
), uintptr(src
), t
.size
)
317 memmove(dst
, src
, t
.size
)
320 func recvDirect(t
*_type
, sg
*sudog
, dst unsafe
.Pointer
) {
321 // dst is on our stack or the heap, src is on another stack.
322 // The channel is locked, so src will not move during this
325 typeBitsBulkBarrier(t
, uintptr(dst
), uintptr(src
), t
.size
)
326 memmove(dst
, src
, t
.size
)
329 func closechan(c
*hchan
) {
331 panic(plainError("close of nil channel"))
337 panic(plainError("close of closed channel"))
341 callerpc
:= getcallerpc(unsafe
.Pointer(&c
))
342 racewritepc(unsafe
.Pointer(c
), callerpc
, funcPC(closechan
))
343 racerelease(unsafe
.Pointer(c
))
350 // release all readers
352 sg
:= c
.recvq
.dequeue()
357 typedmemclr(c
.elemtype
, sg
.elem
)
360 if sg
.releasetime
!= 0 {
361 sg
.releasetime
= cputicks()
366 raceacquireg(gp
, unsafe
.Pointer(c
))
368 gp
.schedlink
.set(glist
)
372 // release all writers (they will panic)
374 sg
:= c
.sendq
.dequeue()
379 if sg
.releasetime
!= 0 {
380 sg
.releasetime
= cputicks()
385 raceacquireg(gp
, unsafe
.Pointer(c
))
387 gp
.schedlink
.set(glist
)
392 // Ready all Gs now that we've dropped the channel lock.
395 glist
= glist
.schedlink
.ptr()
401 // entry points for <- c from compiled code
403 func chanrecv1(t
*chantype
, c
*hchan
, elem unsafe
.Pointer
) {
404 chanrecv(t
, c
, elem
, true)
408 func chanrecv2(t
*chantype
, c
*hchan
, elem unsafe
.Pointer
) (received
bool) {
409 _
, received
= chanrecv(t
, c
, elem
, true)
413 // chanrecv receives on channel c and writes the received data to ep.
414 // ep may be nil, in which case received data is ignored.
415 // If block == false and no elements are available, returns (false, false).
416 // Otherwise, if c is closed, zeros *ep and returns (true, false).
417 // Otherwise, fills in *ep with an element and returns (true, true).
418 // A non-nil ep must point to the heap or the caller's stack.
419 func chanrecv(t
*chantype
, c
*hchan
, ep unsafe
.Pointer
, block
bool) (selected
, received
bool) {
420 // raceenabled: don't need to check ep, as it is always on the stack
421 // or is new memory allocated by reflect.
424 print("chanrecv: chan=", c
, "\n")
431 gopark(nil, nil, "chan receive (nil chan)", traceEvGoStop
, 2)
435 // Fast path: check for failed non-blocking operation without acquiring the lock.
437 // After observing that the channel is not ready for receiving, we observe that the
438 // channel is not closed. Each of these observations is a single word-sized read
439 // (first c.sendq.first or c.qcount, and second c.closed).
440 // Because a channel cannot be reopened, the later observation of the channel
441 // being not closed implies that it was also not closed at the moment of the
442 // first observation. We behave as if we observed the channel at that moment
443 // and report that the receive cannot proceed.
445 // The order of operations is important here: reversing the operations can lead to
446 // incorrect behavior when racing with a close.
447 if !block
&& (c
.dataqsiz
== 0 && c
.sendq
.first
== nil ||
448 c
.dataqsiz
> 0 && atomic
.Loaduint(&c
.qcount
) == 0) &&
449 atomic
.Load(&c
.closed) == 0 {
454 if blockprofilerate
> 0 {
460 if c
.closed != 0 && c
.qcount
== 0 {
462 raceacquire(unsafe
.Pointer(c
))
466 typedmemclr(c
.elemtype
, ep
)
471 if sg
:= c
.sendq
.dequeue(); sg
!= nil {
472 // Found a waiting sender. If buffer is size 0, receive value
473 // directly from sender. Otherwise, receive from head of queue
474 // and add sender's value to the tail of the queue (both map to
475 // the same buffer slot because the queue is full).
476 recv(c
, sg
, ep
, func() { unlock(&c
.lock
) })
481 // Receive directly from queue
482 qp
:= chanbuf(c
, c
.recvx
)
488 typedmemmove(c
.elemtype
, ep
, qp
)
490 typedmemclr(c
.elemtype
, qp
)
492 if c
.recvx
== c
.dataqsiz
{
505 // no sender available: block on this channel.
507 mysg
:= acquireSudog()
510 mysg
.releasetime
= -1
512 // No stack splits between assigning elem and enqueuing mysg
513 // on gp.waiting where copystack can find it.
518 mysg
.selectdone
= nil
521 c
.recvq
.enqueue(mysg
)
522 goparkunlock(&c
.lock
, "chan receive", traceEvGoBlockRecv
, 3)
524 // someone woke us up
525 if mysg
!= gp
.waiting
{
526 throw("G waiting list is corrupted")
529 if mysg
.releasetime
> 0 {
530 blockevent(mysg
.releasetime
-t0
, 2)
532 closed := gp
.param
== nil
539 // recv processes a receive operation on a full channel c.
540 // There are 2 parts:
541 // 1) The value sent by the sender sg is put into the channel
542 // and the sender is woken up to go on its merry way.
543 // 2) The value received by the receiver (the current G) is
545 // For synchronous channels, both values are the same.
546 // For asynchronous channels, the receiver gets its data from
547 // the channel buffer and the sender's data is put in the
549 // Channel c must be full and locked. recv unlocks c with unlockf.
550 // sg must already be dequeued from c.
551 // A non-nil ep must point to the heap or the caller's stack.
552 func recv(c
*hchan
, sg
*sudog
, ep unsafe
.Pointer
, unlockf
func()) {
558 // copy data from sender
559 recvDirect(c
.elemtype
, sg
, ep
)
562 // Queue is full. Take the item at the
563 // head of the queue. Make the sender enqueue
564 // its item at the tail of the queue. Since the
565 // queue is full, those are both the same slot.
566 qp
:= chanbuf(c
, c
.recvx
)
570 raceacquireg(sg
.g
, qp
)
571 racereleaseg(sg
.g
, qp
)
573 // copy data from queue to receiver
575 typedmemmove(c
.elemtype
, ep
, qp
)
577 // copy data from sender to queue
578 typedmemmove(c
.elemtype
, qp
, sg
.elem
)
580 if c
.recvx
== c
.dataqsiz
{
583 c
.sendx
= c
.recvx
// c.sendx = (c.sendx+1) % c.dataqsiz
588 gp
.param
= unsafe
.Pointer(sg
)
589 if sg
.releasetime
!= 0 {
590 sg
.releasetime
= cputicks()
595 // compiler implements
606 // if selectnbsend(c, v) {
612 func selectnbsend(t
*chantype
, c
*hchan
, elem unsafe
.Pointer
) (selected
bool) {
613 return chansend(t
, c
, elem
, false, getcallerpc(unsafe
.Pointer(&t
)))
616 // compiler implements
627 // if selectnbrecv(&v, c) {
633 func selectnbrecv(t
*chantype
, elem unsafe
.Pointer
, c
*hchan
) (selected
bool) {
634 selected
, _
= chanrecv(t
, c
, elem
, false)
638 // compiler implements
649 // if c != nil && selectnbrecv2(&v, &ok, c) {
655 func selectnbrecv2(t
*chantype
, elem unsafe
.Pointer
, received
*bool, c
*hchan
) (selected
bool) {
656 // TODO(khr): just return 2 values from this function, now that it is in Go.
657 selected
, *received
= chanrecv(t
, c
, elem
, false)
661 //go:linkname reflect_chansend reflect.chansend
662 func reflect_chansend(t
*chantype
, c
*hchan
, elem unsafe
.Pointer
, nb
bool) (selected
bool) {
663 return chansend(t
, c
, elem
, !nb
, getcallerpc(unsafe
.Pointer(&t
)))
666 //go:linkname reflect_chanrecv reflect.chanrecv
667 func reflect_chanrecv(t
*chantype
, c
*hchan
, nb
bool, elem unsafe
.Pointer
) (selected
bool, received
bool) {
668 return chanrecv(t
, c
, elem
, !nb
)
671 //go:linkname reflect_chanlen reflect.chanlen
672 func reflect_chanlen(c
*hchan
) int {
679 //go:linkname reflect_chancap reflect.chancap
680 func reflect_chancap(c
*hchan
) int {
684 return int(c
.dataqsiz
)
687 //go:linkname reflect_chanclose reflect.chanclose
688 func reflect_chanclose(c
*hchan
) {
692 func (q
*waitq
) enqueue(sgp
*sudog
) {
706 func (q
*waitq
) dequeue() *sudog
{
719 sgp
.next
= nil // mark as removed (see dequeueSudog)
722 // if sgp participates in a select and is already signaled, ignore it
723 if sgp
.selectdone
!= nil {
724 // claim the right to signal
725 if *sgp
.selectdone
!= 0 ||
!atomic
.Cas(sgp
.selectdone
, 0, 1) {
734 func racesync(c
*hchan
, sg
*sudog
) {
735 racerelease(chanbuf(c
, 0))
736 raceacquireg(sg
.g
, chanbuf(c
, 0))
737 racereleaseg(sg
.g
, chanbuf(c
, 0))
738 raceacquire(chanbuf(c
, 0))