A translation of the cognitive "Golang: channels implementation" article on how the channels are organized in Go.

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

Channel device

Let's start by analyzing the channel structure:

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

In general, a gorutina captures a mutex when it performs an action with a channel, except for 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 not closed. These fields will be further excluded from the overall picture, for clarity.

The channel can be synchronous (unbuffered) or asynchronous (buffered). Let's first look at how synchronous channels work.

Synchronous channels

Suppose 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 dataqsiz is zero. In the above code, there is no guarantee that the first thing will happen - reading from the channel or writing, so let's assume that the first action will be reading from the channel (the opposite example, when recording is first, will be discussed below in the example with buffered channels). Initially, the current gorutina will perform some checks, such as: whether the channel is closed, whether it is buffered or not, whether the gourtas are in the send queue. In our example, the channel does not have a buffer or waiting for sending a gorutin, so the gorutin will add itself to recvq and block. In this step, our channel will look like this:

Now we have only one working gorutin, which is trying to write data to the channel. All checks are repeated again, and when Gorutin checks the recvq queue, she finds the Gorutin waiting for reading, removes it from the queue, writes data to its stack, and removes the lock. This is the only place in all Go rantayme when one gorutina writes directly to the stack of another gorutina. After this step, the channel looks exactly the same as immediately after initialization. Both gorutiny completed and the program goes.

This is how 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 of the first reading gorutina we disassembled above, so now let us assume that two values ​​were written to the channel, and after that one of the elements was read. And the first step is to create a channel that will look like this:

The difference in comparison with the synchronous channel is that here Go allocates a buffer and sets the dataqsiz value to one.

The next step is to send the first value to the channel. To do this, gorutina first performs several checks: is the recvq queue empty, is the buffer empty, is there enough space in the buffer.

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

In the next step, the main gorutin sends the next value to the channel. When the buffer is full, the buffered channel will behave in the same way as a synchronous (unbuffered) channel, that is, a Gorutin will add itself to the waiting queue and will be blocked, as a result, the channel will look like this:

Now the main gorutin is blocked and Go has launched one anonymous gorutin that is trying to read the value from the channel. And here begins the tricky part. Go guarantees that the channel works on the principle of FIFO queue ( specification ), but Gorutin cannot just take a value from the buffer and continue execution. In this case, the main gorutin is blocked forever. To solve this situation, the current gorutina reads data from the buffer, then adds the value from the locked gorutina to the buffer, unlocks the pending gorutina, and removes it from the wait queue. (In the case, if there are no pending Gorutin, it simply reads the first value from the buffer)

Select

But wait, Go still supports select with default behavior, and if the channel is blocked, how can a gorutina be able to handle default? Good question, let's quickly look at the channel APIs private. 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) 

chantype is the type of the channel (for example, bool in the case of make (chan bool)), hchan is a pointer to the channel structure, ep is a pointer to the memory segment where the data from the channel should be written, and last, but the 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, the gorutin checks the buffer and the queue, returns true and writes data to ep or returns false if 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 mutex locking.

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

We figured out how to write and read from the channel, let's now look at what happens when you close the channel.

Channel closure

Closing a channel is a simple operation. Go goes through all the gorutines waiting to read or write and unlocks them. All recipients receive default values ​​for 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 simply as possible, so I missed some details. The purpose of the article is to provide a basic understanding of the internal structure of the channels and push you to read the Go source codes if you want to gain 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.

Links

Source
Channels in the Go specification
Go channels on steroids