Channel: An Important Feature in Golang and an Important Embodiment of the Golang CSP Concurrency Model

Channel is a very important feature in Golang and also an important manifestation of the Golang CSP concurrency model. Simply put, communication between goroutines can be carried out through channels.

Channel is so important in Golang and is used so frequently in code that one cannot help but be curious about its internal implementation. This article will analyze the internal implementation principles of channels based on the source code of Go 1.13.

Basic Usage of Channel

Before formally analyzing the implementation of channels, let's first look at the most basic usage of channels. The code is as follows:

package main
import "fmt"

func main() {
    c := make(chan int)

    go func() {
        c <- 1 // send to channel
    }()

    x := <-c // recv from channel

    fmt.Println(x)
}

In the above code, we create a channel of type int through make(chan int). In one goroutine, we use c <- 1 to send data to the channel. In the main goroutine, we read data from the channel through x := <- c and assign it to x.

The above code corresponds to two basic operations of channels:

The send operation c <- 1, which means sending data to the channel.
The recv operation x := <- c, which means receiving data from the channel.

In addition, channels are divided into buffered channels and unbuffered channels. In the above code, we use an unbuffered channel. For an unbuffered channel, if there is no other goroutine currently receiving data from the channel, the sender will block at the sending statement.

We can specify the buffer size when initializing the channel. For example, make(chan int, 2) specifies a buffer size of 2. Before the buffer is full, the sender can send data to the channel without blocking and does not need to wait for the receiver to be ready. However, if the buffer is full, the sender will still block.

Underlying Implementation Functions of Channel

Before exploring the source code of channels, we must first find out where the specific implementation of channels in Golang is. Because when we use channels, we use the <- symbol, and we cannot directly find its implementation in the Go source code. However, the Golang compiler will surely translate the <- symbol into the corresponding underlying implementation.

We can use the Go's built-in command: go tool compile -N -l -S hello.go to translate the code into corresponding assembly instructions.

Alternatively, we can directly use the online tool Compiler Explorer. For the above example code, you can directly view its assembly results at this link: go.godbolt.org/z/3xw5Cj. As shown in the following figure:

Channel Assembly Instructions

By carefully examining the assembly instructions corresponding to the above example code, the following correspondences can be found:

The channel construction statement make(chan int) corresponds to the runtime.makechan function.
The sending statement c <- 1 corresponds to the runtime.chansend1 function.
The receiving statement x := <- c corresponds to the runtime.chanrecv1 function.

The implementations of the above functions are all located in the runtime/chan.go code file in the Go source code. Next, we will explore the implementation of channels by targeting these functions.

Channel Construction

The channel construction statement make(chan int) will be translated by the Golang compiler into the runtime.makechan function, and its function signature is as follows:

func makechan(t *chantype, size int) *hchan

Here, t *chantype is the element type passed in when constructing the channel. size int is the buffer size of the channel specified by the user, and it is 0 if not specified. The return value of this function is *hchan. hchan is the internal implementation of channels in Golang. Its definition is as follows:

type hchan struct {
        qcount   uint           // The number of elements already placed in the buffer
        dataqsiz uint           // The buf size specified when the user constructs the channel
        buf      unsafe.Pointer // buffer
        elemsize uint16         // The size of each element in the buffer
        closed   uint32         // Whether the channel is closed, == 0 means not closed
        elemtype *_type         // Type information of channel elements
        sendx    uint           // The index position of sent elements in the buffer send index
        recvx    uint           // The index position of received elements in the buffer receive index
        recvq    waitq          // List of goroutines waiting to receive recv waiters
        sendq    waitq          // List of goroutines waiting to send send waiters

        lock mutex
}

All the attributes in hchan can be roughly divided into three categories:

Buffer-related attributes: such as buf, dataqsiz, qcount, etc. When the buffer size of the channel is not 0, the buffer stores the data to be received. It is implemented using a ring buffer.
waitq-related attributes: It can be understood as a standard FIFO queue. Among them, recvq contains goroutines waiting to receive data, and sendq contains goroutines waiting to send data. waitq is implemented using a doubly linked list.
Other attributes: such as lock, elemtype, closed, etc.

The whole process of makechan is basically some legality checks and memory allocation for buffer, hchan and other attributes, and we will not discuss it in depth here. Those interested can directly look at the source code here.

By simply analyzing the attributes of hchan, we can know that there are two important components, buffer and waitq. All the behaviors and implementations of hchan revolve around these two components.

Sending Data into Channel

The sending and receiving processes of channels are very similar. Let's first analyze the sending process of channels (such as c <- 1), which corresponds to the implementation of the runtime.chansend function.

When attempting to send data to a channel, if the recvq queue is not empty, a goroutine waiting to receive data will first be taken out from the head of recvq. And the data will be directly sent to this goroutine. The code is as follows:

if sg := c.recvq.dequeue(); sg!= nil {
        send(c, sg, ep, func() { unlock(&c.lock) }, 3)
        return true
}

recvq contains goroutines waiting to receive data. When a goroutine uses the recv operation (for example, x := <- c), if there is no data in the channel's cache at this time and there is no other goroutine waiting to send data (that is, sendq is empty), this goroutine and the address of the data to be received will be packaged into a sudog object and put into recvq.

Continuing with the above code, if recvq is not empty at this time, the send function will be called to copy the data onto the stack of the corresponding goroutine.

The implementation of the send function mainly includes two points:

memmove(dst, src, t.size) performs data transfer, which is essentially a memory copy.
goready(gp, skip+1) The function of goready is to wake up the corresponding goroutine.

If the recvq queue is empty, it means that there is no goroutine waiting to receive data at this time, and then the channel will try to put the data into the buffer. The code is as follows:

if c.qcount < c.dataqsiz {
        // Equivalent to c.buf[c.sendx]
        qp := chanbuf(c, c.sendx)
        // Copy the data into the buffer
        typedmemmove(c.elemtype, qp, ep)
        c.sendx++
        if c.sendx == c.dataqsiz {
                c.sendx = 0
        }
        c.qcount++
        unlock(&c.lock)
        return true
}

The function of the above code is actually very simple, that is, just putting the data into the buffer. This process involves the operation of the ring buffer, where dataqsiz represents the buffer size of the channel specified by the user, and it defaults to 0 if not specified. Other specific detailed operations will be described in detail in the ring buffer section later.

If the user uses an unbuffered channel or the buffer is full at this time, the condition c.qcount < c.dataqsiz will not be met, and the above process will not be executed. At this time, the current goroutine and the data to be sent will be put into the sendq queue, and this goroutine will be cut out at the same time. The entire process corresponds to the following code:

gp := getg()
mysg := acquireSudog()
mysg.releasetime = 0
if t0!= 0 {
        mysg.releasetime = -1
}
mysg.elem = ep
mysg.waitlink = nil
mysg.g = gp
mysg.isSelect = false
mysg.c = c
gp.waiting = mysg
gp.param = nil
c.sendq.enqueue(mysg)
// Switch the goroutine to the waiting state and unlock
goparkunlock(&c.lock, waitReasonChanSend, traceEvGoBlockSend, 3)

In the above code, goparkunlock unlocks the input mutex and cuts out this goroutine, setting this goroutine to the waiting state. gopark and goready above correspond to each other and are inverse operations. gopark and goready are often encountered in the runtime source code and involve the scheduling process of goroutines, which will not be discussed in depth here, and a separate article will be written about them later.

After calling gopark, from the user's perspective, the code statement for sending data to the channel will block.

The above process is the internal workflow of the channel's sending statement (such as c <- 1), and the entire sending process uses c.lock for locking to ensure concurrent security.

In simple terms, the whole process is as follows:

Check whether recvq is empty. If it is not empty, take a goroutine from the head of recvq, send data to it, and wake up the corresponding goroutine.
If recvq is empty, put the data into the buffer.
If the buffer is full, package the data to be sent and the current goroutine into a sudog object and put it into sendq. And set the current goroutine to the waiting state.

The Process of Receiving Data from Channel

The process of receiving data from a channel is basically similar to the sending process and will not be repeated here. The specific buffer-related operations involved in the receiving process will be described in detail later.

It should be noted here that the entire sending and receiving processes of channels use runtime.mutex for locking. runtime.mutex is a lightweight lock commonly used in the runtime-related source code. The whole process is not the most efficient lock-free approach. There is an issue in Golang: go/issues#8899, which gives a lock-free channel solution.

Implementation of Channel's Ring Buffer

Channels use ring buffers to cache written data. Ring buffers have many advantages and are very suitable for implementing fixed-length FIFO queues.

In channels, the implementation of the ring buffer is as follows:

Implementation of the Ring Buffer in Channel

There are two variables related to the buffer in hchan: recvx and sendx. Among them, sendx represents the writable index in the buffer, and recvx represents the readable index in the buffer. The elements between recvx and sendx represent the data that has been normally placed in the buffer.

We can directly use buf[recvx] to read the first element of the queue, and use buf[sendx] = x to place elements at the end of the queue.

Buffer Writing

When the buffer is not full, the operation of putting data into the buffer is as follows:

qp := chanbuf(c, c.sendx)
// Copy the data into the buffer
typedmemmove(c.elemtype, qp, ep)
c.sendx++
if c.sendx == c.dataqsiz {
        c.sendx = 0
}
c.qcount++

Here, chanbuf(c, c.sendx) is equivalent to c.buf[c.sendx]. The above process is very simple, that is, copying the data to the position of sendx in the buffer.

Then, move sendx to the next position. If sendx has reached the last position, set it to 0, which is a typical head-to-tail connection method.

Buffer Reading

When the buffer is not full, sendq must also be empty at this time (because if the buffer is not full, the goroutine used to send data will not queue up but directly put data into the buffer. For specific logic, refer to the section of sending data to the channel above). At this time, the reading process chanrecv of the channel is relatively simple, and data can be directly read from the buffer, which is also a process of moving recvx. It is basically the same as the buffer writing above.

When there are waiting goroutines in sendq, the buffer must be full at this time. The reading logic of the channel at this time is as follows:

// Equivalent to c.buf[c.recvx]
qp := chanbuf(c, c.recvx)
// Copy data from the queue to the receiver
if ep!= nil {
        typedmemmove(c.elemtype, ep, qp)
}
// Copy data from the sender to the 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

In the above code, ep is the address corresponding to the variable receiving data. For example, in x := <- c, ep represents the address of the variable x. And sg represents the first sudog taken out from sendq. And:

typedmemmove(c.elemtype, ep, qp) means copying the currently readable element in the buffer to the address of the receiving variable.
typedmemmove(c.elemtype, qp, sg.elem) means copying the data waiting to be sent by the goroutine in sendq into the buffer. Because recv++ is performed later, it is equivalent to putting the data in sendq at the end of the queue.

In simple terms, here the channel copies the first data in the buffer to the corresponding receiving variable, and at the same time copies the elements in sendq to the end of the queue, so that data can be processed in FIFO (First In First Out).

Summary

As one of the most commonly used facilities in Golang, understanding the source code of channels can help us better understand and use them. At the same time, we will not be overly superstitious and dependent on the performance of channels. There is still much room for optimization in the current design of channels.

Optimization Notes:

Titles (using # and ##, etc.) are used to layer the article content, making the structure clearer.
Code blocks are clearly marked (using go), enhancing the readability of the code.
The comments in the code blocks are listed separately, making the explanation of the code logic clearer and avoiding the influence of comments in the code blocks on reading experience.
Some key parts are presented in points, making complex logic easier to understand, such as the sending process of channels.
Hyperlinks are added to some content to facilitate readers to consult relevant materials.