How Linux epoll Works: Red-Black Trees and Ready Lists

Linux network daemons, web servers, and event loops spend most of their execution cycles waiting on file descriptor state transitions. For over two decades, the epoll subsystem has formed the bedrock of asynchronous I/O multiplexing on Linux. When an application calls select() or poll(), the kernel iterates across linear arrays of file descriptors on every invocation, paying an $O(N)$ tax that collapses performance at tens of thousands of connections. Understanding how Linux epoll works requires stripping away the userspace abstractions and inspecting the kernel-space data structures that convert linear scans into $O(1)$ event notifications.

The subsystem shifts registration from query time to configuration time. When a process registers a file descriptor with epoll_ctl(), the Linux kernel constructs an internal monitor that attaches directly to the socket or file's underlying wait queue. When network packets land in ring buffers and softirqs process the ingress frames, hardware-driven wakeups trigger kernel callbacks that immediately place active descriptors onto a ready list. The subsequent epoll_wait() invocation merely harvests whatever has already gathered on that list.

Yet despite its ubiquity in runtimes like Tokio, Netty, Node.js, and Envoy, the actual micro-mechanisms governing kernel wakeups, spinlocks, file reference counts, and edge-triggered state machines remain obscured behind a simple triad of system calls. Examining the kernel source code inside fs/eventpoll.c reveals how these data structures coordinate under concurrency and where performance bottlenecks still hide.

Kernel State: Inside struct eventpoll and epitem

The entire lifecycle of an epoll instance centers around an internal kernel object: struct eventpoll. When userspace calls epoll_create1(0), the kernel allocates this structure from the slab allocator and returns a standard file descriptor referencing an anonymous inode created via anon_inodefs.

Inside struct eventpoll, two distinct data structures manage monitored file descriptors and incoming events:

struct eventpoll {
    struct mutex mtx;
    wait_queue_head_t wq;
    wait_queue_head_t poll_wait;
    struct list_head rdllist;
    rwlock_t lock;
    struct rb_root_cached rbr;
    struct epitem *ovflist;
    struct user_struct *user;
    struct file *file;
    /* additional housekeeping fields omitted */
};

The red-black tree rooted at rbr maintains all file descriptors registered with the instance. Each node in this tree is an instance of struct epitem. The red-black tree provides $O(\log N)$ insertion, lookup, and deletion by keying each entry on both the file pointer address (struct file *) and the integer file descriptor number. This compound key allows a process to register duplicated descriptors pointing to the same underlying file description while avoiding collisions.

The doubly linked list rdllist stores only those struct epitem objects that have active events waiting for userspace processing. When no I/O events are pending, rdllist is empty. The presence of rdllist separates epoll from earlier multiplexing syscalls: instead of inspecting every registered descriptor to see if something changed, epoll_wait() only touches entries present on rdllist.

The item tracking each registered descriptor, struct epitem, links these structures together:

struct epitem {
    union {
        struct rb_node rbn;
        struct rcu_head rcu;
    };
    struct list_head rdllink;
    struct epitem *next;
    struct epoll_filefd ffd;
    int nwait;
    struct list_head pwqlist;
    struct eventpoll *ep;
    struct epoll_event event;
};

The ffd member bundles the target file descriptor integer and underlying struct file pointer. The rdllink list head anchors the item into eventpoll->rdllist whenever the monitored socket or file reports a matching event mask. Crucially, pwqlist contains the wait queue attachments that bind the epitem directly to the target device's notification queue.

How Linux epoll Works Across Syscall Boundaries

The userspace API consists of three primary system calls: epoll_create1(), epoll_ctl(), and epoll_wait(). Tracing their execution through the kernel shows how operations transition between userspace memory and internal slab allocations.

When calling epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &event), the kernel routes the request to do_epoll_ctl(). The kernel resolves both epfd and fd from the task's file descriptor table, verifying that epfd is indeed an epoll instance and that fd supports polling via the f_op->poll operation vector. If validation passes, the kernel acquires ep->mtx to serialize modifications to the epoll tree.

Next, ep_insert() allocates a new struct epitem using kmem_cache_zalloc(). The kernel writes the target event mask (EPOLLIN, EPOLLOUT, EPOLLET, etc.) into epi->event. It then calls the target file's poll callback by initializing an ep_pqueue wrapper structure containing a function pointer to ep_ptable_queue_proc().

struct ep_pqueue {
    poll_table pt;
    struct epitem *epi;
};

When vfs_poll() executes on the underlying file—such as a network socket running tcp_poll()—it invokes poll_wait(), which in turn executes ep_ptable_queue_proc(). This function allocates a struct eppoll_entry wait queue item, sets its private callback function to ep_poll_callback(), and inserts it directly into the socket's internal wait queue head (sk->sk_wq.wait).

/* Simplified logical flow inside ep_ptable_queue_proc */
static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead,
                                 poll_table *pt)
{
    struct epitem *epi = ep_item_from_epqueue(pt);
    struct eppoll_entry *pwq;

    if (epi->nwait >= 0 && (pwq = kmem_cache_alloc(pwq_cache, GFP_KERNEL))) {
        init_waitqueue_func_entry(&pwq->wait, ep_poll_callback);
        pwq->whead = whead;
        pwq->base = epi;
        add_wait_queue(whead, &pwq->wait);
        list_add_tail(&pwq->llink, &epi->pwqlist);
        epi->nwait++;
    } else {
        epi->nwait = -1;
    }
}

Once wait queue registration completes, the kernel checks whether the file is already ready by examining the mask returned from vfs_poll(). If events are already active, ep_insert() immediately places the epitem on ep->rdllist and wakes any threads blocked in epoll_wait(). Finally, the item is inserted into the cached red-black tree ep->rbr.

When operations transition toward modern high-speed storage devices rather than sockets, applications often compare epoll with asynchronous submission interfaces. For an examination of how completion rings bypass these registration and wait overheads entirely, see io_uring vs pread: How Batched NVMe I/O Actually Scales.

Wait Queue Registration and ep_poll_callback Execution

The core mechanism delivering $O(1)$ efficiency is ep_poll_callback(). This function executes in interrupt or softirq context when the monitored file descriptor receives data.

Consider a TCP socket receiving an incoming packet from a network interface card:

1. The NIC triggers an MSI-X interrupt, and the driver allocates a socket buffer (sk_buff).
2. The kernel's NET_RX_SOFTIRQ scheduler runs tcp_v4_rcv(), verifying checksums and appending the payload to the socket's receive queue (sk_receive_queue).
3. The networking stack calls sk->sk_data_ready(sk), which resolves to sock_def_readable().
4. sock_def_readable() executes wake_up_interruptible_sync_poll(&sk->sk_wq.wait, EPOLLIN | ...).
5. The wait queue iteration loops through all registered entries, invoking pwq->wait.func, which points directly to ep_poll_callback().

When ep_poll_callback() runs, it retrieves the struct epitem pointer via container_of(). It acquires the spinlock ep->lock to guard list operations. It checks whether the events reported by the wakeup mask match the events requested by userspace.

If matching events exist, the function checks if the epitem is already linked into ep->rdllist. If the item is not on the ready list, it links epi->rdllink to ep->rdllist.

However, a race condition exists: what happens if userspace is actively reading ep->rdllist via epoll_wait() at the exact moment this softirq fires?

To handle this, struct eventpoll includes a secondary list pointer called ovflist. While epoll_wait() processes ready events and copies them to userspace, it sets ep->ovflist to point to a temporary terminator rather than EP_UNACTIVE_PTR. If ep_poll_callback() detects that ep->ovflist is active, it chains the newly readied epitem onto ep->ovflist instead of touching rdllist. Once epoll_wait() finishes its copy pass, it re-acquires ep->lock, transfers all items from ovflist back onto rdllist, and resets ovflist to EP_UNACTIVE_PTR.

After ensuring the item is tracked, ep_poll_callback() checks if any threads are sleeping on ep->wq. If a thread is blocked inside epoll_wait(), the callback calls wake_up(&ep->wq) to transition that task back to TASK_RUNNING.

To inspect or verify these hook points on live production machines without attaching invasive debuggers, engineers trace wait queue registrations with eBPF probes. Techniques used to inspect and verify these kernel hooks are covered in How Linux eBPF Rootkits Evade Detection in Production.

Edge-Triggered vs Level-Triggered Event Delivery Mechanics

The behavioral difference between level-triggered mode (EPOLLLT, the default) and edge-triggered mode (EPOLLET) changes how epoll_wait() manages epitem lifecycle inside ep_send_events().

/* Conceptual flow inside ep_send_events_proc */
static __poll_t ep_send_events_proc(struct eventpoll *ep, struct list_head *head,
                                   void *priv)
{
    struct epitem *epi, *tmp;
    struct epoll_event __user *uevent;
    __poll_t revents;

    list_for_each_entry_safe(epi, tmp, head, rdllink) {
        list_del_init(&epi->rdllink);
        revents = ep_item_poll(epi, &pt, 1);
        if (!revents)
            continue;

        if (__copy_to_user(&uevent[esed->res], &epi->event, sizeof(struct epoll_event)))
            return -EFAULT;

        esed->res++;

        if (!(epi->event.events & EPOLLET)) {
            /* Level-triggered: Re-queue back to ready list */
            list_add_tail(&epi->rdllink, &ep->rdllist);
        }
    }
    return 0;
}

When epoll_wait() runs:

1. It checks if ep->rdllist contains entries. If empty, the calling thread adds itself to ep->wq and sets its state to TASK_INTERRUPTIBLE.
2. When items arrive, the kernel splices ep->rdllist onto a private stack-allocated linked list under ep->lock.
3. The kernel loops over each epitem on the spliced list. For each entry, it queries the file status again via ep_item_poll() to retrieve the accurate, instantaneous event state.
4. It copies the struct epoll_event to userspace buffer memory using __copy_to_user().
5. Here the fundamental divergence occurs:
   • In level-triggered mode (!(epi->event.events & EPOLLET)), the kernel checks if the descriptor is still ready. If unread bytes remain in the socket's receive buffer, ep_item_poll() returns non-zero. The kernel immediately re-adds epi->rdllink back to ep->rdllist.
   • In edge-triggered mode (epi->event.events & EPOLLET), the kernel does not re-add the item to ep->rdllist. The item remains detached from the ready list until another hardware interrupt or socket event arrives and calls ep_poll_callback().

Because edge-triggered mode leaves the item detached, the application must completely consume the underlying resource until receiving an error. If an edge-triggered socket reader reads only a portion of incoming bytes and stops, the kernel will not notify the process again, leaving the socket stalled indefinitely.

Here is the standard POSIX pattern required to safely drain an edge-triggered file descriptor:

#define MAX_EVENTS 64
#define BUFFER_SIZE 4096

void handle_edge_triggered_fd(int epfd, int fd) {
    char buf[BUFFER_SIZE];
    ssize_t bytes_read;

    while (1) {
        bytes_read = read(fd, buf, sizeof(buf));
        if (bytes_read > 0) {
            process_data(buf, bytes_read);
        } else if (bytes_read == -1) {
            if (errno == EAGAIN || errno == EWOULDBLOCK) {
                /* All available data drained; descriptor is empty */
                break;
            }
            perror("read error");
            close(fd);
            break;
        } else {
            /* EOF received from peer */
            close(fd);
            break;
        }
    }
}

Setting EPOLLONESHOT takes edge-triggered semantics one step further: once an event is reported to userspace, the kernel clears the event mask entirely. The file descriptor remains in the red-black tree, but the kernel will ignore subsequent wakeups from ep_poll_callback() until userspace explicitly calls epoll_ctl() with EPOLL_CTL_MOD to reactivate the descriptor.

Lock Contention, Thundering Herds, and Multi-Core Scaling

While epoll scales to millions of idle connections, high-throughput multi-threaded architectures expose mechanical limits inside eventpoll.c.

When multiple worker threads share a single epoll file descriptor, all threads sleep on the single wait queue head ep->wq. When a single connection receives incoming data, the default wake behavior wakes up all threads sleeping on that queue. All threads attempt to acquire ep->lock and ep->mtx simultaneously. One thread succeeds in dequeuing the item; the remaining threads burn CPU cycles context-switching only to receive zero events. This is the classic epoll thundering herd problem.

Linux 4.5 introduced the EPOLLEXCLUSIVE flag for EPOLL_CTL_ADD. When set, the wait queue mechanism sets the WQ_FLAG_EXCLUSIVE bit on the epoll wait item. When wake_up() executes, the scheduler terminates the traversal after waking exactly one exclusive waiter, preventing the cascade of spurious wakeups across worker threads.

However, EPOLLEXCLUSIVE does not solve spinlock contention on ep->lock when event rates climb into millions of operations per second across dozens of cores. Because every ready list manipulation requires holding ep->lock, multi-threaded architectures that funnel events through a single epoll handle become serialized by the memory bus.

To avoid this, modern high-performance runtimes use a thread-per-core design:

[ Worker Thread 0 ] ---> [ Dedicated epoll fd ] ---> Sub-set of Sockets
[ Worker Thread 1 ] ---> [ Dedicated epoll fd ] ---> Sub-set of Sockets
[ Worker Thread 2 ] ---> [ Dedicated epoll fd ] ---> Sub-set of Sockets
[ Worker Thread 3 ] ---> [ Dedicated epoll fd ] ---> Sub-set of Sockets

In this model, each thread owns an isolated epoll instance and services a segregated partition of connections. New connections are distributed across threads by passing the SO_REUSEPORT socket option to listening sockets. The kernel's TCP stack hashes the incoming connection's 4-tuple and places the newly established socket directly into the queue of one specific listening thread.

This thread-per-core model eliminates inter-core spinlock bouncing on struct eventpoll. However, managing large buffers per thread increases resident set sizes, placing pressure on the virtual memory subsystem. For an analysis of how page-table walks and memory allocations impact thread latency under load, refer to Why Transparent Huge Pages on a VPS Degrade Memory Latency.

Another scaling bottleneck occurs during rapid connection churn. If an application opens and closes thousands of short-lived connections per second, calling epoll_ctl(EPOLL_CTL_ADD) and epoll_ctl(EPOLL_CTL_DEL) requires frequent acquisitions of ep->mtx. In ep_remove(), unlinking the item from the wait queue requires ep_unregister_pollwait(), followed by freeing the epitem via Read-Copy-Update (call_rcu()). Under high churn, the RCU callback lists and mutex acquisition overheads outpace the cost of the actual socket I/O.

Conclusion

The epoll subsystem achieves scalable I/O multiplexing by shifting work out of the critical path. Rather than paying an $O(N)$ tax to query thousands of descriptors on each tick, epoll_create1() and epoll_ctl() build a stateful monitoring framework directly into kernel memory.

A red-black tree inside struct eventpoll indexes registered descriptors with $O(\log N)$ search and modification guarantees. Wait queue hooks registered during epoll_ctl() invoke ep_poll_callback() directly from network softirq contexts, moving only active struct epitem objects onto rdllist. When userspace calls epoll_wait(), the kernel merely detaches the accumulated ready list, checks instantaneous device status, and copies the events to userspace memory.

Level-triggered operations preserve unread items on the ready list for subsequent iterations, while edge-triggered mode requires userspace to drain descriptors until encountering EAGAIN. Scalability at modern multi-core scale depends on avoiding shared-instance lock contention: by pairing thread-per-core architectures with SO_REUSEPORT or applying EPOLLEXCLUSIVE, systems architects eliminate spinlock contention on ep->lock and extract deterministic latency from the Linux networking stack.

Measured on our own hardware: Do Transparent Huge Pages Help on a VPS? Random Access Over 1 GiB

On this virtual server, does asking the kernel for 2 MiB transparent huge pages make a dependent random read over a 1 GiB buffer faster than the same buffer on 4 KiB pages, and how much of the buffer actually gets huge pages?

We ran it. The numbers below come from a program executed on the server hosting this site on 2026-09-20 — an AMD EPYC 9354P 32-Core Processor with 8 cores visible, 31.3 GB of memory, Linux 6.8.0-139-generic.

Metric	Value
huge page speedup factor	1.66
accesses	50000000
buffer mib	1024
checksum	61078
huge case anon huge pages kb	1048576
huge case fraction backed by 2m pages	1
huge pages ns per access best	165.96
huge pages ns per access mean	168.09
mode	measure
pages 2m in buffer	512
pages 4k in buffer	262144
repeats	5
small case anon huge pages kb	0
small pages ns per access best	275.62
small pages ns per access mean	289.73

This is a shared virtual server, not an isolated test rig, so treat the absolute figures as indicative and the ratio between the two cases as the finding. The full method, the machine specification, and the complete source code are on the Do Transparent Huge Pages Help on a VPS? Random Access Over 1 GiB benchmark page, so you can check the method or run it yourself.

Measured on our own hardware: io_uring vs pread: Random Reads at Queue Depth 32

How many random 4 KiB reads per second can one thread sustain with serial pread() syscalls, compared with io_uring submitting 32 at a time, when the page cache is taken out of the picture?

We ran it. The numbers below come from a program executed on the server hosting this site on 2026-09-20 — an AMD EPYC 9354P 32-Core Processor with 8 cores visible, 31.3 GB of memory, Linux 6.8.0-139-generic.

Metric	Value
io uring speedup factor	7.85
block bytes	4096
blocks read	20000
io uring best seconds	0.4712
io uring iops	42449
o direct	true
pread best seconds	3.6977
pread iops	5409
pread mean latency us	184.88
queue depth	32
repeats	3

This is a shared virtual server, not an isolated test rig, so treat the absolute figures as indicative and the ratio between the two cases as the finding. The full method, the machine specification, and the complete source code are on the io_uring vs pread: Random Reads at Queue Depth 32 benchmark page, so you can check the method or run it yourself.

References

1. The Linux Kernel Organization. fs/eventpoll.c source code. Available at: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/fs/eventpoll.c
2. Linux Programmer's Manual. epoll(7) — I/O event notification facility. Available at: https://man7.org/linux/man-pages/man7/epoll.7.html
3. Corbet, Jonathan. Epoll scalability and EPOLLEXCLUSIVE. LWN.net. Available at: https://lwn.net/Articles/632590/