How the channels are arranged in Go

Original author: Dmitry Vorobev
  • Transfer

Translation of the informative article "Golang: channels implementation" on how channels are arranged in Go.


Go is becoming more and more popular, and one of the reasons for this is its excellent support for competitive programming. Channels and goroutines greatly simplify the development of competitive programs. There are some good articles about how various data structures are implemented in Go - for example, slices , maps , interfaces - but quite a bit has been written about the internal implementation of channels. In this article, we will explore how channels work and how they are implemented internally. (If you've never used feeds in Go, I recommend reading this article first .)


Channel device


Let's start by parsing the channel structure:



  • qcount - the number of elements in the buffer
  • dataqsiz - buffer dimension
  • buf - buffer pointer for channel elements
  • closed - a flag indicating whether the channel is closed or not
  • recvq - pointer to a linked list of goroutines waiting to be read from the channel
  • sendq - pointer to a linked list of goroutines waiting to write to the channel
  • lock - mutex for secure access to the channel

In general, goroutine captures a mutex when it performs an action with a channel, except in cases of lock-free checks for non-blocking calls (I will explain this in more detail below). Closed is a flag that is set to 1 if the channel is closed, and to 0 if it is not closed. These fields will be further excluded from the overall picture, for greater clarity.


A channel can be synchronous (unbuffered) or asynchronous (buffered). Let's first see how synchronized channels work.


Synchronous channels


Let's say we have the following code:


package main
func main() {
    ch := make(chan bool)
    go func() {
        ch <- true
    }()
    <-ch
}

First, a new channel is created and it looks like this:



Go does not allocate a buffer for synchronous channels, so the pointer to the buffer is nil and dataqsizequal to zero. The above code does not guarantee that the first thing will happen - reading from the channel or writing, so suppose that the first action is reading from the channel (the reverse example, when recording is first started, will be discussed below in the example with buffered channels). First, the current goroutine will perform some checks, such as: whether the channel is closed, whether it is buffered or not, whether the gourtines are in send queues. In our example, the channel has neither a buffer nor goroutines waiting to be sent, so goroutin will add itself to recvqand be blocked. At this step, our channel will look like this:



Now we only have one working goroutine who is trying to write data to the channel. All checks are repeated again, and when the goroutine checks the recvqqueue, it finds the goroutine waiting to be read, removes it from the queue, writes data to its stack and unlocks it. This is the only place in the entire Go runtime when one goroutine writes directly to the stack of another goroutine. After this step, the channel looks exactly the same as immediately after initialization. Both goroutines end and the program exits.


So the synchronous channels are arranged. Now, let's look at buffered channels.


Buffered Channels


Consider the following example:


package main
func main() {
    ch := make(chan bool, 1)
    ch <- true
    go func() {
        <-ch
    }()
    ch <- true
}

Again, the order of execution is unknown, the example with the first reading goroutine we have examined above, so now we assume that two values ​​were recorded in the channel, and after that one of the elements is subtracted. And the first step is to create a channel that looks like this:



The difference compared to the synchronous channel is that Go selects a buffer and sets the value dataqsizto one.


The next step is to send the first value to the channel. To do this, goroutine first makes several checks: whether the queue recvqis empty, whether the buffer is empty, whether there is enough space in the buffer.


In our case, there is enough space in the buffer and there are no goroutines in the queue for reading, so goroutine simply writes the element to the buffer, increases the value qcountand continues execution further. The channel at this moment looks like this:



In the next step, goroutine main sends the next value to the channel. When the buffer is full, the buffered channel will behave exactly like a synchronous (unbuffered) channel, i.e. goroutine will add itself to the wait queue and block, as a result, the channel will look like this:



Now goroutine main is blocked and Go has launched one anonymous goroutine that is trying to read the value from the channel. And here the tricky part begins. Go guarantees that the channel works on the basis of the FIFO queue ( specification ), but goroutine cannot simply take the value from the buffer and continue execution. In this case, goroutine main will be blocked forever. To solve this situation, the current goroutine reads data from the buffer, then adds the value from the blocked goroutine to the buffer, unlocks the waiting goroutine, and removes it from the wait queue. (If there is no one waiting for goroutine, it simply reads the first value from the buffer)


Select


But wait a minute, Go also supports select with default behavior, and if the channel is blocked, how can goroutin handle default? Good question, let's take a quick look at the private channels API. When you run the following piece of code:


    select {
    case <-ch:
        foo()
    default:
        bar()
    }

Go runs the function with the following signature:


func chanrecv(t *chantype, c *hchan, ep unsafe.Pointer, block bool)

chantypethis is the type of channel (for example, bool in the case of make (chan bool)), hchanis a pointer to the structure of the channel, epis a pointer to the memory segment where the data from the channel should be written, and the last, but most interesting for us, is the argument block. If it is set to false, then the function will work in non-blocking mode. In this mode, goroutine checks the buffer and queue, returns trueand writes data to epor returns falseif there is no data in the buffer or there are no senders in the queue. Buffer and queue checks are implemented as atomic operations, and do not require locking the mutex.


There is also a function for writing data to a queue with a similar signature.


We figured out how recording and reading from a channel work, let's now take a look at what happens when a channel closes.


Channel closure


Closing a channel is a simple operation. Go goes through all the goroutines awaiting reading or writing and unlocks them. All recipients receive the default value of the variables of that type of channel data, and all senders panic.


Conclusion


In this article, we looked at how channels are implemented and how they work. I tried to describe them as simple as possible, so I missed some details. The purpose of this article is to provide a basic understanding of the internal structure of channels and encourage you to read the Go source code if you want a deeper understanding. Just read the channel implementation code . It seems to me very simple, well-documented and rather short, only about 700 lines of code.


References


Source code
Channels in the Go specification Go
channels on steroids


Also popular now: