Understand epoll in depth

Before we begin, let me ask you a few questions.

1. How high is epoll performance? Many articles have described how ePoll can easily handle hundreds of thousands of connections. The performance of epoll is thousands of times that of traditional IO, which can handle only a few hundred connections.

2. Many articles divide network IO into blocking, non-blocking, synchronous and asynchronous. Non-blocking performance is better than blocking performance, and asynchronous performance is better than synchronous performance.

• If blocking causes poor performance, why would traditional IO block?
• Does epoll need to block?
• Java NIO and AIO are both implemented in epoll. How to understand the difference between synchronous and asynchronous?

3, are IO multiplexing.

• Why have there been select, poll and epoll?
• Why is epoll performing better than Select?

PS:

This paper consists of three parts: introduction to Epoll, principle behind epoll and Diss.

The focus of this article is to introduce the principle, and the reader is advised to focus as much as possible on: “why”.

The difference between a process and a thread on Linux isn’t that great, especially when discussing principles and performance issues, so the terms “process” and “thread” are used interchangeably in this article.

Using an example of a network card receiving data, let’s review the process of a network card receiving data that I shared earlier.



For the sake of understanding, I’ve tried to simplify the technical details as much as possible by dividing the process of receiving data into four steps:

1. The NIC receives the data and writes it to memory (Ring Buffer and SK_buff) via DMA.
2. The NIC issues an interrupt request (IRQ) to tell the kernel that new data is coming.
3. The Linux kernel responds to the Interrupt, switching to kernel mode, processing the Interrupt Handler, taking a Packet from the RingBuffer, processing the protocol stack, filling the Socket and handing it to the user process.
4. The system switches to user mode, and user processes process data content.

When the network card receives data depends on the sender and the transmission path, and the latency is usually very high, in milliseconds (ms). Applications process data at the nanosecond (NS) level. That is to say, the whole process, the kernel state waiting for data, processing the protocol stack is a relatively slow process. There is nothing for the user mode process to do for such a long time, hence the use of “blocking”.

Of course, the kernel can easily change the state of a process. The problem is which process the kernel should change in network IO.

Socket structure, which contains two important data: process ID and port number. The process ID holds the connect, send, read suspended process. When a socket is created, the port number is determined. The operating system maintains a data structure with a port number into the socket.

When the nic receives data, the data must contain a port number, and the kernel can find the socket and get the ID of the “pending” process. Change the state of the process to Runnable (join the work queue). At this point the kernel code completes execution and returns control to the user state. User processes can process data through normal “CPU slice scheduling.”

There are two areas of the procedure described above that cause frequent context switches and can be inefficient.

1. If data packets are received frequently, the NIC may issue frequent interrupt requests (IRQs). The CPU may be in user mode, it may be in kernel mode, it may still be working on the protocol stack of the previous piece of data. However, the CPU must respond to the interrupt as soon as possible. Doing so is actually quite inefficient, causing a lot of context switching and potentially leaving the user process without data for a long time. (Even if it is multi-core, the protocol stack is not finished each time, naturally cannot be handed to the user process)
2. Each Packet corresponds to a socket, and each socket corresponds to a user-mode process. When these user-mode processes become “runnable”, context switching between processes is inevitable.

The kernel optimization technique for “interprocess context switching” is called “IO multiplexing”, which is very similar to NAPI.

Each socket no longer blocks the process that reads or writes it, but instead uses a dedicated thread to process user-mode data in batches, thus reducing context switching between threads.

As an implementation of IO multiplexing, the principle of SELECT is very simple. All sockets store the process ID that executes the select function. Any socket that receives data wakes up the monitor process. The kernel simply tells the monitor that those sockets are ready, and the monitor can process them in batches.

Select, Poll, and ePoll are all “IO multiplexing”, so why the performance gap? Space is limited, so let’s just briefly compare the fundamental differences between SELECT and epoll.

For the kernel, there may be many sockets being processed at the same time, and there may be several monitoring processes. So every time a monitoring process “batches data,” it needs to tell the kernel about the socket it cares about. When the kernel wakes up the monitoring process, it can pass the ready socket in the Concerned Socket to the monitoring process.

In other words, when the system call SELECT or epoll_CREATE is executed, the input parameter is “concerned socket” and the output parameter is “ready socket.”

The difference between SELECT and epoll is that:

Select (one O(n) lookup)

1. An FD_set of user-space allocations passed to the kernel one at a time is used to represent “sockets of concern.” Its structure (equivalent to a bitset) limits it to 1024 sockets.
2. Each time the socket state changes, the kernel queries O(1) with fd_set to see if the monitoring process cares about the socket.
3. The kernel reuses fd_set as an output parameter and returns it to the monitoring process (so each select input parameter needs to be reset).

However, the monitoring process must traverse the socket array O(n) to know which sockets are ready.

Epoll (all O(1) lookups)

1. Pass the kernel one instance handle at a time. The handle is the kernel assigned red-black tree RBR + bidirectional linked list RDLList. As long as the handle stays the same, the kernel can reuse the result of the last calculation.
2. Each time the socket state changes, the kernel can quickly query O(1) from the RBR to monitor whether the process cares about the socket. Also modify the RDLList, so that the RDLList is actually a cache of ready sockets.
3. The kernel copies some or all of the RDLList (LT and ET) to a special epoll_event as an output parameter.

So the monitoring process can process data directly one by one, without having to iterate through the validation.

Also, it doesn’t really matter whether the underlying implementation of epoll_create is a red-black tree or not (hashTable could have been used instead). The important thing is that efDS are Pointers, and their data structures can be transparently modified to any other data structure.

We’ve spent three chapters explaining the principles behind Epoll, and now we can sum it up in three sentences.

1. Based on the basic principle of data sending and receiving, the system improves CPU utilization by using blocking.
2. “IO multiplexing” (and NAPI) is designed to optimize live text switching.
3. Three versions of the API(SELECT, Poll, and epoll) were designed to optimize the interaction between the kernel and the monitoring process.

The classification of blocking, non-blocking, synchronous, and asynchronous makes sense. But from an operating system perspective ** “this classification is misleading and not good” **.

All IO models under Linux are synchronized. BIO is synchronous, SELECT is synchronous, Poll is synchronous, ePoll is still synchronous.

Java provides AIO that might be called “asynchronous.” But the JVM runs in user mode, and Linux does not provide any asynchronous support. So the asynchronous support provided by the JVM is not fundamentally different from the “asynchronous” framework that you package yourself (which you can easily package using BIO).

Synchronous and asynchronous are just two event Dispatchers or design patterns (Reactor and Proactor). Since both are running in user mode, how much performance difference can there be between the two design modes?

• Reactor corresponds to Java’S NIO, the core API of channels, buffers, and selectors.
• Proactor corresponds to Java’s AIO, the API that forms the core of the Async component and Future or Callback.

Does epoll use Mmap at all?

Answer: No!

It was a false rumour. And it’s actually pretty easy to prove, let’s do a demo with epoll. Strace makes it clear.