§ 36 — Kernel Wait Queue Internals

§ 36.1 — wait_queue_head_t & wait_queue_entry_t

Every blocking object in the Linux kernel — a socket, a pipe, a timer — owns a wait_queue_head_t. Processes that need to sleep until the object becomes ready add a wait_queue_entry_t to that list, then call schedule(). When data arrives the object calls wake_up(), which iterates the list and invokes each entry's func callback.

wait_queue_head Linked List

A socket's sk_wq→wait is a typical head. At any moment it may hold entries from multiple select processes and an epoll instance simultaneously — each entry has a different func that controls what happens at wakeup.

wait_queue_entry_t Field Annotations

The func field is the kernel's primary extensibility hook: select installs pollwake, epoll installs ep_poll_callback. The same wakeup machinery handles both, yet the per-entry callback determines whether waking means “rescan all fds” (select) or “add one epitem to rdllist” (epoll).

Struct Definitions

struct wait_queue_head {
    spinlock_t        lock;
    struct list_head  head;
};

struct wait_queue_entry {
    unsigned int        flags;   /* WQ_FLAG_EXCLUSIVE etc. */
    void               *private; /* sleeping task_struct * */
    wait_queue_func_t   func;    /* callback on wakeup */
    struct list_head    entry;   /* link in wait_queue_head.head */
};

§ 36.2 — How a Process Enters Sleep

Both select and epoll must register on socket wait queues to be notified when data arrives — but when and how many entries they insert differ fundamentally. select inserts one entry per fd at every call; epoll inserts entries at epoll_ctl(ADD) time and only one entry on its own wait queue at epoll_wait.

select() Sleep Path

epoll_wait() Sleep Path

Side-by-Side: Registration Cost

Interactive: Wait Queue Registration Visualizer

Switch between select and epoll mode, adjust the number of monitored fds, and call the syscall to see how many wait queue entries are inserted — and how much memory is consumed per call.

§ 36.3 — How a Process is Woken Up

When data arrives on a socket, sk_data_ready() calls wake_up(), which runs __wake_up_common() — a single loop over the socket's wait queue. Every entry's func callback fires. For select that means re-scanning all N fds; for epoll it means appending one epitem to the ready list in O(1).

__wake_up_common Traversal

pollwake vs ep_poll_callback

Interactive: Wakeup Callback Comparison

Set N (monitored fds) and trigger a data-arrives event. Watch select scan all N fds via vfs_poll() while epoll adds a single epitem to rdllist in O(1).

§ 36.4 — WQ_FLAG_EXCLUSIVE & Thundering Herd

When multiple processes wait on the same event — for example, worker threads all blocked on accept() for the same listen socket — a single new connection wakes all of them. Only one can succeed; the rest return EAGAIN and sleep again. This thundering herd wastes N−1 context switches per event. WQ_FLAG_EXCLUSIVE fixes it by telling __wake_up_common to stop after waking the first exclusive waiter.

Without WQ_FLAG_EXCLUSIVE — Thundering Herd

With WQ_FLAG_EXCLUSIVE

EPOLLEXCLUSIVE Example

/* EPOLLEXCLUSIVE example */
struct epoll_event ev = {
    .events = EPOLLIN | EPOLLEXCLUSIVE,
    .data.fd = listenfd,
};
epoll_ctl(epfd, EPOLL_CTL_ADD, listenfd, &ev);
/* kernel: eppoll_entry.wait.flags |= WQ_FLAG_EXCLUSIVE
   __wake_up_common stops after 1 exclusive entry is woken */

add_wait_queue_exclusive() inserts the entry at the tail of the wait queue, after all non-exclusive entries. This ensures non-exclusive waiters (e.g. poll() monitors) are still woken first, while exclusive waiters compete only one-at-a-time.

§ 36.5 — Cleanup: Removing Wait Queue Entries

The asymmetry between select and epoll is most visible in cleanup cost. Every select() call must add N entries before sleeping and remove all N entries on return — even if no fd was ready. At high call rates this dominates CPU time. epoll socket entries are installed once at epoll_ctl(ADD) and survive across all subsequent epoll_wait() calls; each wait only touches a single entry on ep->wq.

select / poll — Per-Call Overhead

epoll — Register Once, Wait Many Times

select Cleanup — poll_freewait()

/* select cleanup on return (net/core/poll.c) */
void poll_freewait(struct poll_wqueues *pwq) {
    struct poll_table_page *p = pwq->table;
    while (p) {
        struct poll_table_entry *e = p->entries;
        remove_wait_queue(e->wait_address, &e->wait); /* N times */
        fput(e->filp);
        e++;
        /* free page */
    }
}
/* epoll_wait return: no such cleanup */

Interview Prep — Must-Know Questions