Blocking I/O and readiness

4.6 Waiting for a packet: sleeping, polling and spinning

A packet in a socket’s receive queue is no use until the thread that wants it notices. The thread can sleep and let the kernel wake it; it can ask, over and over, whether anything has come; or it can ask in a way that makes the asking itself pull the packet off the card. The three differ by two orders of magnitude in latency and by a whole core in cost, and the difference is largest exactly when the feed has been quiet. This section is what each does inside the kernel and what it buys.

Blocking read

A socket starts out blocking. A recv that finds its receive queue empty puts the calling thread to sleep on the socket’s wait queue, a list the socket keeps of entries to notify when its state changes. The kernel adds an entry naming the thread, marks the thread as sleeping, and calls the scheduler, which gives the core to another thread or to the idle task. When the softirq’s protocol walk appends a packet’s data to the receive queue, it calls the socket’s data-ready hook, which goes down the wait queue and wakes each entry: the thread is marked runnable and put on a run queue, and if its core is idle or running something less urgent, the core is sent an IPI to make it reschedule now. When the thread next runs, it resumes inside recv, copies the bytes into the program’s buffer and returns.

The cost is Chapter 2’s wake-up: most of the 5–20 µs that the receive path costs a sleeping reader, and 100–200 µs from a deep C-state. A blocking reader also serves only one socket. A thread asleep in recv on the A feed cannot notice a packet on the B feed, or on the order connection, until the A feed sends something.

Read more: Michael Kerrisk’s The Linux Programming Interface covers blocking, non-blocking and multiplexed I/O in its part on alternative I/O models, and the epoll(7) man page is the contract for what follows.

select, poll and epoll

A thread with many sockets needs one call that sleeps until any of them is ready. select, from 1983, takes bitmaps of up to 1,024 descriptors; the kernel checks each and, if none is ready, adds the thread to the wait queue of every one and sleeps, and on waking checks them all again and returns the bitmaps for the program to scan. poll takes an array instead, without the limit, and does the same work. Both cost time in proportion to the number of descriptors watched, on every call, because the kernel keeps nothing between calls.

epoll, Linux’s own, keeps it. epoll_create1 returns a descriptor for an epoll instance, a kernel object holding two structures: the interest list, a balanced tree of the descriptors the program has registered with epoll_ctl, once, each with the events it wants; and the ready list, the registered descriptors that have something to report. On registration epoll puts an entry of its own on the socket’s wait queue, and when the data-ready hook calls it, the entry appends the descriptor to the ready list and wakes any thread sleeping in epoll_wait, which then only takes entries off the ready list. A thread watching 10,000 connections of which two are ready pays for two, which is why every event loop on Linux is built on it.

Each registration is level-triggered or edge-triggered. Level-triggered, the default, reports a descriptor on every epoll_wait for as long as it is readable. Edge-triggered, EPOLLET, reports it when new data arrives and not again until more arrives, so the program must read until recv returns WouldBlock, or the rest sits unannounced until the next packet; it does less work per wait, and it is what mio, the Rust crate that wraps epoll, always uses. The last argument of epoll_wait is a timeout in milliseconds: −1 sleeps until something is ready, a positive value sleeps at most that long, and 0 does not sleep at all, which makes epoll_wait a poll of the ready list.

poll.poll(&mut events, Some(Duration::ZERO)) is the same call with a timeout of 0.

The wake-up path, and why it sets the tail

Whether the thread sleeps in recv or in epoll_wait, the chain is: NIC completion → IRQ/NAPI → protocol processing → socket ready → scheduler wake-up → reader copies data.

Each link is short on a good day and has bad days of its own, which is why the wake-up sets the tail rather than the median. The idle governor picks a core’s C-state from how long it expects the idle spell to last, so the longer the feed has been quiet, the deeper the reader’s core has gone: on a feed of a few hundred updates a second the 100–200 µs exit is the common case, and on a busy one it comes after every lull, for the update that ends it. The interrupt’s core can be asleep too, and then the chain pays two exits. A thread already running on the reader’s core can keep the woken reader waiting for the rest of a slice, milliseconds; a busy interrupt core makes this packet’s walk wait behind others, or behind ksoftirqd; and the reader wakes into cold caches, the colder for a deep C-state, which flushed them.

A timed wait may use timer slack (commonly 50 µs for a normal thread), and scheduling can delay it further, so a 1 ms timeout may return after 1.05 ms or later. A packet still wakes the thread through the chain above, but a loop that sleeps briefly between non-blocking checks, instead of waiting on the socket, may add coalescing and wake-up delay to its requested sleep; slack is not a mandatory lower bound.