[Go] channel in detail

Channel traits:

• goroutine is safe
• store and pass values between goroutines, Golang is a value based language same as C and C++
• provides FIFO semantic
• can cause goroutines to block and unblock

How would you design a channel?

Ring buffer!

With ring buffer, we need:

• the type that this ring buffer holds, thus compiler knows the size of the ring buffer which could allocate it's memory.
• start idx(hchan.recvx), end idx(hchan.sendx) (thus we know the current data size)
  while hchan.recvx == hchan.sendx means either 0 data or ring is full.
• ring buffer size
• how many senders/receivers are consuming the ring
  thus we need mutex lock

Let's take a look at hchan struct in golang chan.go implement:
https://github.com/golang/go/blob/master/src/runtime/chan.go#L32


hchan instance usually allocated on the heap, unless this channel is only been used in one single thread(stack, to be precise).


ch <- 42 will copy data into the ring buffer with mutex locks hchan, increase the hchan.sendx.
<- ch will copy the value from ring buffer with mutex locks hchan, increase the hchan.recvx.


If the ring buffer is full, send blocks, and golang scheduler suspends the send goroutine (aka. user space thread, not the OS thread) until there's room in the ring buffer.

Please refer to previous post about scheduler:
http://vsdmars.blogspot.com/2018/06/golang-go-scheduler.html
Golang scheduler design doc:
https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw


Each (G)oroutine is managed by (P)rocessor, and each (P)rocessor can only be run by one (M)thread.
(P)rocessor has the runQ (list) holds (G)oroutines.

If the ring buffer is full, the sender pauses, scheduler calls 'gopark' to remove the caller (G)oroutine from (M)thread into (P)rocessor's runQ(of (G)oroutines).
https://github.com/golang/go/blob/master/src/runtime/proc.go#L284:6


hchan has the information of senders and receivers.
https://github.com/golang/go/blob/master/src/runtime/chan.go#L53:6

hchan.sendq // waitq
hchan.recvq  // waitq

type waitq struct {
    first *sudog
    last  *sudog
}

sudog:
https://github.com/golang/go/blob/master/src/runtime/runtime2.go#L276

sudog.elem represends the data which is about to send(copy)/receive(copy) to/from the ring buffer.



Here's the interesting part, the implementation optimized sending/receiving data by skip copy data into/out from ring buffer iff there's a waiting (G)oroutine, which directly store the sending/receiving pointer to data into the waiting (G)oroutine's sudog.elem
Receive optimized:
https://github.com/golang/go/blob/master/src/runtime/chan.go#L190
Send optimized:
https://github.com/golang/go/blob/master/src/runtime/chan.go#L473



Fast path implement:
Sender:
https://github.com/golang/go/blob/master/src/runtime/chan.go#L159
Receiver: (atomic.Load involved)
https://github.com/golang/go/blob/master/src/runtime/chan.go#L437


Quote from Ian Lance Taylor:
https://groups.google.com/forum/#!topic/golang-nuts/L-bGvB52UrU
The runtime package is always compiled by a known compiler, and is permitted to know how that specific compiler behaves. If the compiler changes, while still staying within spec, the runtime package will change too. You can't argue about the language's memory model based on the code in the runtime package.


Reference:
Ring buffer in C:
https://embeddedartistry.com/blog/2017/4/6/circular-buffers-in-cc
chan.go:
https://github.com/golang/go/blob/master/src/runtime/chan.go
gopark:
https://github.com/golang/go/blob/master/src/runtime/proc.go#L284:6
goready:
https://github.com/golang/go/blob/master/src/runtime/proc.go#L310:6
Benign Data Races: What Could Possibly Go Wrong?
https://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong
The Go Memory Model:
https://golang.org/ref/mem