Internals of Go Channels

Introduction

In this blog, we are going to understand the internals of channels in Go.

Following are the things that I am covering in this blog.

  1. Overview and basic definition, types, use-cases and properties of channels.
  2. Making of channel, its representation , and initialisation.
  3. Different scenarios of blocking and unblocking of go-routines by channels .
  4. Exchange of messages between go-routines through channel, copying of data objects.
  5. Working of Pausing/Blocking and Resuming/Unblocking of go-routines by channels.
  6. Within it, brief introduction of runtime, scheduling, and
  7. Algorithm of pausing of sender on a full buffered channel (imp)
  8. Algorithm to resume sender on a full buffered channel (imp)
  9. Algorithm to resume receiver on an empty buffered channel (imp)
  10. Unbuffered channels and select statement.

Background

Go Channels are typed tubes/conduit through which different go-routines can communicate. By typed, I mean, channels can only send and receive objects of some type. There are 3 types of channels

  1. asynchronous(buffered)
  2. synchronous(unbuffered)
  3. async channels with zero-sized elements(chan struct{}): These are basically semaphores with nil buffer and O(1) memory

To create a channel of int type, use function

ch := make(chan int) // unbuffered channel
bch := make(chan int, 100) // buffered channel

To send or receive objects from the channel, use operator

ch <- 3 //sends 3 to the channel 
v := <- ch // receives 3 from the channel and assigns it to v

Properties of channels

  1. Used for synchronisation and communication between go routines without explicit locks or condition variables
  2. Internally, works like a FIFO circular queue
  3. Channels transfer the copy of the object.
  4. By default, sends and receives block until the other side is ready. This allows go-routines to synchronise without explicit locks or condition variables.
  5. Sends to a buffered channel block only when the buffer is full. Receives block when the buffer is empty.
  6. zero-value of a channel is
  7. When a go-routine wants to receive data from another go-routine , but never sends the data, then the channel will make to wait indefinitely, and vice versa.
  8. If the buffer is full or if there is nothing to receive, a buffered channel will behave very much like an unbuffered channel.
  9. For unbuffered channel, one go-routine should be in running state, while other go-routine should be in runnable state.

Use-cases of channels

  1. Go-routine safe
  2. Implement FIFO behaviour
  3. Exchange data between go-routines
  4. Block and Unblock go-routines

Making of channel

If we want to have a naive implementation of a channel depicting first two use-cases, we would simply have a lock on a queue(FIFO data-structure). Likewise, implements it as struct.

hchan struct

Available in in package

type hchan struct {
qcount uint // total data in the queue
dataqsiz uint // size of the circular queue
buf unsafe.Pointer // pointer to an array(queue)
elemsize uint16
closed uint32 // if channel is closed
elemtype *_type // element type
sendx uint // send index
recvx uint // receive index
recvq waitq // list of recv waiters
sendq waitq // list of send waiters
lock mutex // mutex for concurrent access to the channel
}

Channels use a circular queue of size , where or point to the next element that is going to be sent to or received from the channel.

Initialisation of channel

While making a channel, allocates struct on a heap and returns a pointer to it. So, is just a pointer to a variable of type .

For synchronous channels, doesn’t allocate any buffer, so will be and will be . For asynchronous channels, will be pointing to head of the circular queue allocated in a heap(> 32 kB) using .

Working of Buffered Channel

Blocking and Unblocking Go-routines

As we all know, channels block and unblock go-routines. Sender go-routine is blocked when the buffer is full or there is no receiver, and similarly, receiver go-routine is blocked when the buffer is empty or there is no sender.

There are two more attributes in struct, and . These are pointers to a doubly linked list of waiting/blocked go-routines. is a pointer to the list of go-routines waiting to send data on the channel(when channel is full or no receiver), whereas is a pointer to the list of go-routines waiting for receiving data from the channel(when channel is empty or no sender).

Refer to unbuffered channel diagram for more understanding.

I have discussed more about the algorithm of pausing and resuming in further sections. Meanwhile, just remember that these two variables store of waiting go-routines.

Send and Receive Messages

In this section, we will be discussing about how go-routines interact with channel for communication and inner workings of channel. Here I am taking single sender and receiver for the sake of simplicity, but the concepts is applicable for multiple senders and receivers.

Main go-routine(G1)

// G1func main() {
tasks := []string{"task1", "task2", "task3"}

ch := make(chan string, 3)

go worker(ch)

for _, task := range tasks {
ch <- task
}
}

worker go-routine(G2)

// G2 func worker(ch chan string) {
for {
t := <- ch
process(t)
}
}

Now when sends a task to a channel(assuming is empty), following actions are taken by the go-runtime.

  1. acquire the lock
  2. make a copy of and it in the .
  3. release the lock and allows on its merry way

The operation is memory . It copies into

Now suppose, is scheduled to receive the data from the channel, following actions are taken by go-runtime

  1. acquire the lock
  2. the from , make a copy and assign it to .
  3. release the lock and allows to go on its merry way.

The important thing to note here is that the copy into and out of the channel buffer is what gives us memory safety. The only shared memory both the go-routines access is which is protected by . Every object is just a copy. This property is what allows channels to align with the principle

Do not communicate by sharing memory; instead, share memory by communicating

Let’s come back to the discussion, now both the go routines and have send and receive the data respectively, and now is empty in the channel.

Now, suppose is taking really long time to process a single task and is incapable of receiving any more tasks from the async channel. But keeps sending more tasks into it without getting blocked.

As you can see, the buffered channel is full, can’t send anymore tasks into it. So, ‘s execution is , only after a receive. Let’s see how does the pausing and resuming works for go-routines with channels. (you can also refer to blocking and unblocking section above.)

Pausing and Resuming of go-routines

Before we can understand pausing and resuming, it is important to understand the scheduling of go-routines.

Go-routines are user-space threads. They are managed by go-runtime scheduler on top of OS threads. Go-routines life-cycle is managed by go-runtime and not OS, that’s why these are lightweight compared to OS threads. These are less expensive in terms of resource consumption, scheduling overhead etc.

Go-runtime scheduler uses M:N scheduling model to schedule these go-routines on top of OS threads. Scheduler multiplexes these M go-routines onto these N OS threads.

Go’s M:N scheduling is described by 3 structs.

g, m, and p structs

These structs can be found in package in

I have listed only few important attributes from all the three structs

type g struct {
...
stack stack // offset known to runtime/cgo
m *m // current m; offset known to arm liblink
...
}type m struct {
...

g0 *g // go-routine with scheduling stack
curg *g // current running go-routine
p puintptr // attached p for executing go code (nil if not executing go code)
nextp puintptr
oldp puintptr // the p that was attached before executing a syscall
id int64
locks int32
blocked bool // m is blocked on a note
createstack [32]uintptr // stack that created this thread.
mOS

...
}
type p struct {
...
m muintptr // back-link to associated m (nil if idle)

// Queue of runnable goroutines. Accessed without lock.
runqhead uint32
runqtail uint32
runq [256]guintptr
sudogcache []*sudog
...
}
Three different structs of go-routines

In order to run go-routines, must hold and must hold , where is basically . holds a which a queue holding runnable go-routines.

During runtime, g holds m and m holds g and p.

Algorithm to pause/block a go-routine

Now let’s understand how does channel and scheduling play their roles while pausing/blocking a go-routine.

Here, I am taking an example a go-routine (G1) trying to send a task on full buffered channel

// G1ch <- task4 // sending task4 on a full channel
  1. When tries to send on a full buffered channel, the channel creates a for itself and attaches it to of struct and then channel makes call to scheduler.
  2. Now, scheduler changes the state of running into waiting state.
  3. Then scheduler, removes the association of from , dequeues the runnable from (held by ), and schedules onto .
  4. Later, when receiver is ready to take another tasks, it dequeues from .
Channel creates sudog and then attaches it sendq
Pausing of go-routine(G1) while trying to send on full channel

This is basically a context switch of go-routines done by runtime scheduler. Observe that when send operation was executed, was running, but by the end of the operation, is running and is blocked. Also note that, OS thread is not blocked.

For more clarity, you can refer to this code snippet of func from file.

// Block on the channel. Some receiver will complete our operation for us.gp := getg()
mysg := acquireSudog()
// No stack splits between assigning elem and enqueuing mysg
// on gp.waiting where copystack can find it.
mysg.elem = ep
mysg.g = gp
mysg.c = c // setting the current channel
gp.waiting = mysg
// enque sudog on channel sendq
c.sendq.enqueue(mysg)
// trigger gopark call
goparkunlock(&c.lock, waitReasonChanSend, traceEvGoBlockSend, 3)
// Ensure the value being sent is kept alive until the
// receiver copies it out. The sudog has a pointer to the
// stack object.
KeepAlive(ep)

Algorithm to resume/unblock a sender go-routine on full channel

Let’s understand how does channel and scheduling play their roles while resuming/unblocking a go-routine. Here I am continuing the same example, but, from receivers end.

Currently, we know that is in waiting state, and holds a containing details of and a copy of , also the is full.

gets schedule onto some OS thread, it is going perform receives on the channel. Note that, channel’s is containing [, , ]

// G2t := <- ch // receives from the buffered channel
  1. Channel first dequeues the object(task1) from , which means it receives , assigns to the variable.
  2. Then, dequeues from , enqueues into . (Important optimisation)
  3. Sets to runnable state. It does this by making a call to runtime scheduler with . This means is telling scheduler to make runnable.
Current state of hchan after receiving
Resuming of go-routine (G1)

Let’s address the important question

Q. Why did enqueue into ?

This is a veery important optimisation. G2 enqueues task4 into channels’ buf so that channel doesn’t have to wait for G1 to get schedule and then enqueue it. Also another advantage is that, for enqueuing object G1 needs to acquire the lock, but now G1 doesn’t have to acquire the lock and it doesn’t have to mess with the channel’s state.

You can refer to following snippet from for func and func . When there is a is not empty calls .

func chanrecv() {
...
if sg := c.sendq.dequeue(); sg != nil {
// Found a waiting sender. If buffer is size 0, receive value
// directly from sender. Otherwise, receive from head of queue
// and add sender's value to tail of the queue (both map to
// the same buffer slot because the queue is full).

recv(c, sg, ep, func() { unlock(&c.lock) }, 3)
return true, true
}
...
}// ep is pointing to caller's stack or a heap.
func recv(c *hchan, sg *sudog, ep unsafe.Pointer, unlockf func(), skip int) {
// Queue is full. Take the item at the
// head of the queue. Make the sender enqueue
// its item at the tail of the queue. Since the
// queue is full, those are both the same slot.
qp := chanbuf(c, c.recvx)
// copy data from queue to receiver
if ep != nil {
typedmemmove(c.elemtype, ep, qp)
}
// copy data from sender to queue
typedmemmove(c.elemtype, qp, sg.elem)
c.recvx++
if c.recvx == c.dataqsiz {
c.recvx = 0
}
c.sendx = c.recvx // c.sendx = (c.sendx+1) % c.dataqsiz
}
sg.elem = nil
gp := sg.g
unlockf()
goready(gp, skip+1)
}
}

Algorithm to resume/unblock a receive go-routine on empty channel

This is very interesting section

In the above section, we discussed about the resuming a sender blocked on full buffered channel. In this, we are going to discuss how does resuming of receiver go-routine takes place while waiting on the empty channel.

// G2t := <- ch

Suppose the channel is empty and scheduler schedules before could send any task on it. Since the channel is empty, will go into waiting(pause/block) state. (refer to pausing algo. and the diagram below)

Following will the state of

Now, gets schedule so we have two options to resume receiver.

Option 1

  • can enqueue the task, dequeue waiting from and call to the scheduler.

Option 2 (smarter way, important optimisation, actual implementation)

  • can directly copy obj into ‘s location from .

Why did directly copy into G2 stack instead enqueuing?

We know all the go-routines have non-overlapping separate stacks, and go-routines don’t access each other states. Here, is directly accessing stack pointer of , and changing the state of it. I know it is not right, but this will save from taking a lock and mess with the channel’s buffer, also one fewer memory copy and hence optimisation.

Resume in unbuffered/synchronous channels

Unbuffered channels always work as direct send case

  1. receiver waiting → sender directly writes to receiver’s stack from
  2. sender waiting → receiver directly writes to sender’s stack from

Code snippet for the same

Sender waiting, receiver receiving from unbuffered channel

// A non-nil ep must point to the heap or the caller's stack.func recv(c *hchan, sg *sudog, ep unsafe.Pointer, unlockf func(), skip int) {   // unbuffered channel
if c.dataqsiz == 0 {
...
if ep != nil {
// copy data from sender to ep
recvDirect(c.elemtype, sg, ep)
}
} else { ...
}
...
sg.elem = nil
gp := sg.g
goready(gp, skip+1)
}

Receiver waiting, sender sends on unbuffered channel

// The value ep sent by the sender is copied to the receiver sg.
// sg must already be dequeued from c.
// ep must be non-nil and point to the heap or the caller's stack.
func send(c *hchan, sg *sudog, ep unsafe.Pointer, unlockf func(), skip int) {
if raceenabled {
if c.dataqsiz == 0 {
racesync(c, sg)
} else {
// Pretend we go through the buffer, even though
// we copy directly. Note that we need to increment
// the head/tail locations only when raceenabled.
qp := chanbuf(c, c.recvx)
...
c.recvx++
if c.recvx == c.dataqsiz {
c.recvx = 0
}
c.sendx = c.recvx
}
}
if sg.elem != nil {
// copy ep of sender to receiver's sg
sendDirect(c.elemtype, sg, ep)
sg.elem = nil
}
gp := sg.g
unlockf()
gp.param = unsafe.Pointer(sg)
if sg.releasetime != 0 {
sg.releasetime = cputicks()
}
goready(gp, skip+1)
}

Select Statement

  1. All channels are locked
  2. A is put in the/ queues of all channels
  3. Channels unlocked, all the selecting G is paused
  4. CAS operation so there is only one winning case
  5. Resuming mirrors the pause sequence.

You can learn more about select statement from package

References

  1. Dmitry Blog
  2. Go Channels on steroids
  3. Kavya Joshi Talk
  4. Golang by example
  5. Journey with Go

A subset of defective homo-sapiens. Busy in Learning…