Epoll vs Select vs Poll: How the Linux Kernel Actually Handles 100k Concurrent Connections

In 1999, Dan Kegel published his classic paper on "The C10K Problem," posing a simple question: how do you design a web server capable of handling 10,000 concurrent client connections on a single machine?

At the time, the standard approach was process-per-connection or thread-per-connection. Web servers like Apache prefork spawned a dedicated thread or process for every active socket. That model collapsed rapidly under load:

1. Stack Memory Overhead: Every thread allocates an execution stack (historically 2MB to 8MB default virtual memory). 10,000 threads meant tens of gigabytes of virtual memory allocated just to keep idle connections alive.
2. Context Switching Penalties: When thousands of threads contend for CPU execution, the Linux kernel scheduler spends more time swapping register contexts, invalidating Translation Lookaside Buffer (TLB) caches, and thrashing L1/L2/L3 CPU caches than executing application logic.
3. I/O Multiplexing Bottlenecks: Early multiplexing system calls like select() and poll() scaled linearly ($O(N)$), degrading dramatically as connection counts climbed.

To scale modern systems like NGINX, Node.js (via libuv), Redis, and Netty to 100,000+ persistent connections, the industry shifted to event-driven architectures powered by epoll(7).

Here is a technical walkthrough of what happens inside the Linux kernel (fs/eventpoll.c and network subsystem) when you multiplex I/O at scale.

---

1. The Fatal Flaws of select() and poll()

To understand why epoll exists, you have to look at what select() and poll() actually force the kernel to do on every invocation.

The select(2) Mechanism

int select(int nfds, fd_set *readfds, fd_set *writefds, 
           fd_set *exceptfds, struct timeval *timeout);

An fd_set is a fixed-size bitmask representing file descriptors. On Linux, FD_SETSIZE defaults to 1024 bits in <sys/select.h>.

User Space                           Kernel Space
+------------------------+           +-----------------------------+
| Bitmask: [0 1 0 0 1 0] | --copy--> | Linear scan 0 to nfds-1     |
|                        |           | Attach to each socket queue |
|                        |           | Sleep if none ready         |
|                        |           | Rescan all sockets on wake  |
| Bitmask: [0 0 0 0 1 0] | <--copy-- | Overwrite bitmask           |
+------------------------+           +-----------------------------+

When you call select():

1. User-to-Kernel Copy: Your application passes bitmasks across the user-space/kernel-space boundary (copy_from_user).
2. Linear Kernel Scan: The kernel iterates through every descriptor from 0 to nfds - 1, checking if file->f_op->poll() reports readiness.
3. Wait Queue Registration: For every socket checked, the kernel registers the current process on the socket's internal wait queue.
4. Sleep & Rescan: If no socket is ready, the process sleeps. When a packet arrives on any socket, the process wakes up and must rescan all nfds sockets again to determine which ones have ready data and construct the output bitmask.
5. Kernel-to-User Copy: The kernel copies the modified bitmasks back to user space (copy_to_user).
6. Destructive Mutation: Because select() overwrites the bitmasks in place, user code must iterate through all descriptors with FD_ISSET() and then rebuild the entire bitmask from scratch before the next call.

The poll(2) Mechanism

poll(2) improved on select() by replacing fixed-size bitmasks with a variable-length array of struct pollfd:

struct pollfd {
    int   fd;       /* file descriptor */
    short events;   /* requested events (POLLIN, POLLOUT) */
    short revents;  /* returned events */
};

This removed the 1024 descriptor ceiling and stopped destructive mask overwriting because events and revents are separate fields.

However, the fundamental $O(N)$ architecture remained identical:

• If you monitor 50,000 sockets, poll() must copy an array of 50,000 structs (400 KB of data) into kernel space on every single call.
• The kernel still iterates across all 50,000 entries one by one to check readiness.
• Your application must loop through all 50,000 entries in user space to check if (fds[i].revents & POLLIN).

select and poll are stateless. The kernel retains no memory of what you were monitoring between calls.

---

2. The Architecture of epoll(7)

Introduced in Linux 2.5.44 by Davide Libenzi, epoll solves the scalability problem by making event monitoring stateful inside the kernel.

Instead of passing thousands of file descriptors on every system call, epoll splits registration from polling into three distinct system calls:

int epoll_create1(int flags);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);

The Kernel Data Structures (fs/eventpoll.c)

When you create an epoll instance via epoll_create1(), the kernel allocates a struct eventpoll containing two foundational data structures:

                  struct eventpoll
          +------------------------------+
          |  Red-Black Tree (rbr)        |  <-- O(log N) storage for all
          |    [fd:3]     [fd:7]         |      monitored sockets (epitems)
          |    /    \     /    \         |
          |  [fd:1] [fd:5]               |
          +------------------------------+
          |  Ready List (rdllist)        |  <-- O(1) doubly-linked list
          |  [epitem: fd 5] <-> [fd 7]   |      containing ONLY active sockets
          +------------------------------+
          |  Wait Queue (wq)             |  <-- Sleeping user threads
          +------------------------------+

Let's look at the underlying structures:

1. The Red-Black Tree (rbr):

   • Stores all monitored file descriptors as struct epitem nodes.
   • Keyed by (struct file *, int fd).
   • Allows $O(\log N)$ lookups, insertions, modifications, and deletions when calling epoll_ctl().
   • Persists in kernel memory across poll cycles.

2. The Ready List (rdllist):

   • A doubly-linked list of struct epitem pointers.
   • Contains only those items that currently have active, unconsumed I/O events.
   • When no sockets have incoming data, this list is empty.

3. The Epoll Item (struct epitem):

   • Represents a monitored socket descriptor inside eventpoll.
   • Contains an embedded RB-tree node (rbn) and an embedded linked-list node (rdllink).
   • Maintains a list of poll wait queues (pwqlist) that hook directly into the socket's internal subsystem.

---

3. The Event Lifecycle: From NIC Packet to epoll_wait

Let's trace what happens when network packets arrive on an epoll-monitored socket.

[ NIC Hardware ]
       |  DMA transfer
[ RAM: rx_ring buffer ]
       |  Hardware Interrupt (HardIRQ)
[ CPU: Top-Half Handler ] -> schedules SoftIRQ
       |
[ NET_RX_SOFTIRQ / NAPI ] -> tcp_v4_rcv() -> sock_def_readable()
       |
[ Wait Queue Callback ] -> ep_poll_callback()
       |
       +---> Adds epitem to eventpoll->rdllist (O(1))
       +---> Wakes up process waiting in epoll_wait()
       |
[ epoll_wait() returns ] -> copies ONLY ready events to user buffer (O(K))

Step 1: Socket Registration (epoll_ctl)

When you execute epoll_ctl(epfd, EPOLL_CTL_ADD, sock_fd, &ev):

1. The kernel allocates a struct epitem for sock_fd.
2. The item is inserted into the eventpoll->rbr Red-Black tree.
3. The kernel calls the driver/socket poll function (vfs_poll) using a custom queue callback: ep_ptable_queue_proc.
4. ep_ptable_queue_proc allocates a struct eppoll_entry and attaches a custom wakeup callback function—ep_poll_callback—directly into the socket's wait queue (sk->sk_wq).

Step 2: Packet Ingestion and TCP Processing

When a remote client sends bytes over the network:

1. The Network Interface Card (NIC) receives the physical Ethernet frames and performs a Direct Memory Access (DMA) transfer to write the raw packets into the kernel's receive ring buffer (rx_ring).
2. The NIC fires a hardware interrupt (HardIRQ) to a CPU core.
3. The CPU runs the minimal top-half interrupt handler, acknowledges the interrupt, and schedules a software interrupt (NET_RX_SOFTIRQ).
4. The NAPI polling loop runs in softirq context, pulls packets from rx_ring, constructs struct sk_buff wrappers, and passes them to ip_rcv() and tcp_v4_rcv().
5. The TCP stack verifies checksums, processes sequence numbers, handles ACKs, and appends the payload into the socket's receive buffer (socket receive queue).

Step 3: The Wakeup Callback (ep_poll_callback)

Once data sits in the socket receive queue, the socket triggers its data-ready hook (sock_def_readable).

In select() or poll(), this would wake up the process directly, forcing it to rescan every socket.

In epoll, sock_def_readable() invokes ep_poll_callback():

/* Simplified logical flow inside fs/eventpoll.c: ep_poll_callback */
static int ep_poll_callback(wait_queue_entry_t *wait, unsigned mode, int sync, void *key)
{
    struct epitem *epi = ep_item_from_wait(wait);
    struct eventpoll *ep = epi->ep;

    /* 1. Check if the socket events match what the user requested */
    poll_table_entry_key(key);

    /* 2. If not already in the ready list, add it in O(1) time */
    if (!ep_is_linked(&epi->rdllink)) {
        list_add_tail(&epi->rdllink, &ep->rdllist);
    }

    /* 3. Wake up any threads blocked in epoll_wait() */
    if (waitqueue_active(&ep->wq)) {
        wake_up(&ep->wq);
    }
    return 1;
}

This callback is the core reason epoll scales. It executes in $O(1)$ time, linking the specific epitem to eventpoll->rdllist without touching any other monitored socket.

Step 4: Event Retrieval (epoll_wait)

When your application thread calls epoll_wait():

1. The kernel checks eventpoll->rdllist.
2. If rdllist is empty, the thread puts itself to sleep on eventpoll->wq with zero CPU overhead.
3. Once rdllist contains items (populated by ep_poll_callback), the thread wakes up.
4. The kernel walks rdllist, transfers up to maxevents items, calls ep_item_poll() to confirm current state, and writes the struct epoll_event array directly into user space memory.
5. If $K$ sockets are ready out of 100,000 total connections, the kernel only touches and returns those $K$ sockets.

Complexity comparison:

Operation	select(2)	poll(2)	epoll(7)
Active Monitoring Complexity	$O(N)$	$O(N)$	$O(K)$ ready events
Descriptor Registration	$O(N)$ per call	$O(N)$ per call	$O(\log N)$ once
User/Kernel Memory Copy	Copies all $N$ FDs every call	Copies all $N$ FDs every call	Copies only $K$ active events
Max Descriptor Limit	1024 (FD_SETSIZE)	System limit (RLIMIT_NOFILE)	System limit (RLIMIT_NOFILE)
Kernel State Retention	Stateless	Stateless	Stateful

---

4. Level-Triggered (LT) vs Edge-Triggered (ET)

When configuring epoll_ctl, you can select between two trigger modes:

ev.events = EPOLLIN;            /* Level-Triggered (Default) */
ev.events = EPOLLIN | EPOLLET;  /* Edge-Triggered */

Understanding their behavioral difference is critical to avoid socket hangs or CPU starvation.

Buffer State:  [EMPTY]  ----->  [DATA ARRIVES: 4KB]  ----->  [READ 2KB: 2KB LEFT]
                                        |                             |
Level-Triggered (LT):             Fires EPOLLIN                 Fires EPOLLIN again
                                  (Buffer not empty)            (Buffer still not empty)
                                        |                             |
Edge-Triggered (ET):              Fires EPOLLIN once            NO EVENT FIRED
                                  (0 -> 4KB edge transition)    (State didn't change from 0)

1. Level-Triggered (Default)

• Behavior: As long as the underlying socket buffer contains unread data, epoll_wait() will continue reporting the descriptor as ready on every subsequent call.
• Safety: Forgiving. If your application reads only part of a message, it will be notified again on the next event loop iteration.
• Cost: Extra iterations and kernel checks if data remains in the buffer across multiple cycles.

2. Edge-Triggered (EPOLLET)

• Behavior: An event is generated only when the descriptor transitions from not ready to ready (e.g., when new data arrives on an empty socket buffer).
• The Contract:
  1. The socket must be set to non-blocking mode (O_NONBLOCK).
  2. When epoll_wait() returns an ET socket, you must loop read() or recv() until it returns EAGAIN or EWOULDBLOCK.

/* Correct Edge-Triggered consumption pattern */
while (1) {
    ssize_t count = read(fd, buf, sizeof(buf));
    if (count == -1) {
        if (errno == EAGAIN || errno == EWOULDBLOCK) {
            /* All available data drained; return to epoll_wait */
            break;
        }
        perror("read error");
        close(fd);
        break;
    } else if (count == 0) {
        /* Client closed connection */
        close(fd);
        break;
    }
    process_data(buf, count);
}

What happens if you break early?
If you read 2 KB of a 4 KB payload and exit the loop without hitting EAGAIN, the remaining 2 KB stays buffered in the kernel. Because the state did not transition from empty to non-empty, no new edge-triggered event will ever fire, and that connection stalls indefinitely until new data arrives to trigger another edge.

The Starvation Risk in Edge-Triggered Loops:
If a single malicious client continuously streams gigabytes of data into a socket, a naive while (1) loop will never return EAGAIN, monopolizing the event loop thread and starving all other 99,999 connections. Production event loops implement read budgets (e.g., max 64 KB or 16 iterations per socket before yielding back to epoll_wait).

---

5. Thundering Herd and Multi-Threaded Epoll

When building multi-core servers, you frequently have multiple worker threads sharing incoming traffic.

The Problem

If multiple threads share a single epfd or call epoll_wait() on the same listening socket, a single incoming connection can wake up all sleeping threads simultaneously. One thread successfully calls accept(), while all other threads receive EAGAIN, wasting CPU cycles on context switches.

Kernel Solutions

1. EPOLLEXCLUSIVE (Linux 4.5+): When registering a socket with EPOLLEXCLUSIVE, the kernel wakes up only a single waiting thread in epoll_wait() when an event arrives, eliminating the thundering herd for shared listen sockets.
2. SO_REUSEPORT: Enables multiple independent sockets (each with their own epoll instance and thread) to bind to the exact same port. The Linux kernel distributes incoming TCP connections across the sockets using an internal hash:

Port 443 Listen Queue (SO_REUSEPORT)
         |
    Kernel Hash [src_ip, src_port, dst_ip, dst_port]
    /         |         \
Worker 1   Worker 2   Worker 3
(epoll 1)  (epoll 2)  (epoll 3)

Each worker thread runs its own isolated epoll_wait() loop with zero lock contention.

---

6. Beyond Epoll: The Shift to io_uring

While epoll solved the C10K problem, high-throughput modern systems handling millions of IOPS face a new constraint: syscall overhead.

epoll is a readiness-based model:

1. epoll_wait() tells you a socket is ready to read (Syscall 1).
2. Your application calls read() to pull bytes into user memory (Syscall 2).
3. Your application processes data and calls write() to send a response (Syscall 3).

Each transition between user space and kernel space incurs CPU register saves, stack adjustments, and CPU speculation barriers (Spectre/Meltdown mitigations).

Readiness (epoll):
User space   --- epoll_wait() ---> Kernel (is fd ready?)
User space   <-- returns ready --- Kernel
User space   --- read() ---------> Kernel (copies data)
User space   <-- returns data ---- Kernel

Completion (io_uring):
User space   --- writes SQE into ring buffer ---> (No immediate syscall)
Kernel       --- async DMA & process -------> (Background kernel poller)
User space   <-- reads CQE from ring buffer ---- (Zero syscalls via SQPOLL)

In Linux 5.1, Jens Axboe introduced io_uring, a completion-based asynchronous I/O framework.

io_uring uses two lockless ring buffers mapped in shared memory between user space and the kernel:

• Submission Queue (SQ): User space posts I/O requests (read, write, accept).
• Completion Queue (CQ): The kernel posts completed results.

With IORING_SETUP_SQPOLL, a dedicated kernel thread continuously polls the Submission Queue. An application can submit thousands of reads and writes and receive completed data buffers with zero system calls, representing the next major evolution beyond epoll.

---

7. Practical Mental Model

When reasoning about Linux networking and event loops:

• select() / poll(): The kernel is stateless. You hand the kernel a list of everything you care about on every tick; the kernel linearly checks all of them.
• epoll(): The kernel is stateful. Monitored descriptors live in a persistent Red-Black tree. Socket drivers hook ep_poll_callback to place ready sockets onto a doubly-linked list in $O(1)$ time upon packet arrival.
• Level-Triggered: Notifies as long as the buffer is non-empty. Easy to write, resilient against partial reads.
• Edge-Triggered: Notifies only on state transitions. Requires non-blocking sockets and exhaustive draining until EAGAIN.
• io_uring: Replaces readiness polling and individual read()/write() syscalls with asynchronous completion queues in shared memory.