The I/O subsystem

Why this matters

A CPU executes billions of operations per second. An SSD access takes tens of microseconds, a network round trip takes milliseconds, and a human at the keyboard takes whole seconds. Seven orders of magnitude separate the speed of the CPU from the speed of everything else, and almost the entire I/O subsystem exists to hide that gap.

You see the consequences every day. Why doesn’t copying a file load the CPU to one hundred percent? Why does a web server with a thread per connection fall over at ten thousand clients while one built on epoll doesn’t? Why does strace show a program spending ninety percent of its time in read? It is all one topic.

Prerequisites. Interrupts and DMA (module 2), the user/kernel boundary and the cost of a system call (module 3), the “blocked” state of processes.

Devices from the kernel’s point of view

There are thousands of devices, but the kernel doesn’t need to know about each one. The driver reduces any device to one of two models.

A block device works with fixed-size blocks and random access: you can read block 5000 and then block 12. Disks, SSDs and USB drives are block devices, and file systems are built on top of them.

A character device works with a stream of bytes and no random access. That’s a keyboard, a serial port, /dev/random, a sound card. Rewinding is usually not an option.

The split is purely practical: block devices get a cache and request scheduling, character devices don’t, because there is no point in caching or reordering a stream.

The driver gives the kernel the same set of operations: open, read, write, control. That is why read() behaves the same for a file on NVMe, for a socket and for /dev/null: all the differences are hidden in the driver.

Who moves the data

The most expensive question in the whole I/O subsystem is this: who moves the bytes from the device controller into main memory.

Three generations of answers to one question. The shaded area is CPU time spent servicing the transfer instead of doing useful work.

With polling, the CPU checks a status register in a loop: ready? ready? ready? It also moves the data itself. Simple to implement and catastrophically wasteful, because for the whole transfer the CPU is busy doing nothing but waiting.

With interrupts, the CPU starts the operation and goes off to run other processes. When the device is ready, it raises an interrupt line, the CPU stops its current work and runs the handler. CPU time is spent only on handlers, though a handler fires for every block of data.

DMA hands the transfer to a direct memory access controller, which does everything on its own without the CPU. The kernel gives it a buffer address and a size, and in return gets a single interrupt when everything is done. That is why copying a gigabyte file doesn’t load a CPU core: the data goes around it.

Polling isn't dead

On very fast devices an interrupt becomes more expensive than waiting. An NVMe drive can return a block faster than it costs to enter an interrupt handler and return from it, so Linux has a hybrid io_poll mode: start by polling and switch to interrupts if the response is late.

The rule “polling is wasteful” was derived for slow devices and no longer holds for fast ones.

The path of one read()

1. The process calls read(fd, buf, n). The CPU switches to kernel mode.

2. Using the number fd, the kernel finds the file object in the open file table, and through it the driver that owns the object.

3. If the data is already in the page cache, the kernel copies it into the process’s buffer and returns. The device isn’t touched at all.

4. If the data isn’t there, the driver queues a request to the device, and the process is moved to the “blocked” state and taken off the CPU.

5. The controller performs the operation and uses DMA to put the data into kernel memory. An interrupt arrives.

6. The interrupt handler marks the request as complete and moves the process to the “ready” state. The scheduler will put it back on the CPU when its turn comes.

7. The kernel copies the data from the cache into the process’s buffer, and read returns the number of bytes.

Two items on this list are worth remembering. Step three explains why reading the same file a second time is instant: the page cache does the work, and the disk isn’t even touched. Step four explains why a program that seems to be doing nothing shows state S in ps: it is blocked in read and isn’t using the CPU.

Buffering and caching

Two different things that people regularly confuse.

Buffering reconciles speeds and sizes. The device returns data in blocks of 512 bytes, the program asks for three at a time, so a buffer is needed between them. On top of that, the data can’t be handed to the process in pieces until the operation has finished.

Caching keeps a copy of what has already been read in case it’s read again. All free RAM in Linux is taken up by the page cache, and that’s the normal state: free shows it in the buff/cache column, and it is released instantly as soon as processes need it.

Hence the consequence that scares beginners: “I only have 300 MB free out of 16 GB.” Look at the available column, not at free. Memory used by the cache is not used up.

Blocking and non-blocking I/O

By default a descriptor is blocking, meaning read won’t return until there is data. For one file that’s convenient, but for a server with ten thousand connections it isn’t: to wait on ten thousand descriptors you would need ten thousand threads, each with its own stack and its own share of context switches.

The way out was to ask the kernel about all descriptors at once: which of them are ready right now.

Mechanism	Cost per call	Problem
select	O(n), limited to 1024 descriptors	the list is passed in again every time
poll	O(n), no hard limit	same thing: the kernel scans the whole list every time
epoll	O(ready)	the descriptor set lives in the kernel, only ready ones are returned
io_uring	O(ready), no system call per operation	the most complex API of the three

epoll became the foundation of every modern server because the cost of a call depends on the number of ready descriptors and not on the total. Nine thousand nine hundred sleeping connections cost nothing.

io_uring goes further and removes the system call itself. The program and the kernel share two ring queues in shared memory: requests go into one, results are picked up from the other. Under heavy load this saves millions of switches into kernel mode per second.

Non-blocking doesn't mean asynchronous

A non-blocking read returns EAGAIN when there is no data, and the program has to ask again later. Asynchronous I/O accepts a request and reports completion on its own. In other words, epoll reports readiness, and io_uring reports completion.

Mixing up the two produces architectures that poll in a loop for the thing that was supposed to wake them up.

How it actually works in Linux

lsblk -o NAME,TYPE,SIZE,ROTA,SCHED,MODEL

The system’s block devices. ROTA=1 means a spinning disk, 0 means an SSD. SCHED shows the request scheduler for that device (module 14).

ls -l /dev/null /dev/sda /dev/tty 2>/dev/null

The first character is the type: c for a character device, b for a block device. Instead of a size, a device file shows two numbers: the major and minor numbers, which the kernel uses to find the driver.

grep -E 'NVME|nvme|eth|xhci' /proc/interrupts | head

Interrupt counters by source and by CPU core. The columns correspond to cores; if all of a network card’s interrupts land on one core, that core becomes a bottleneck before the rest.

free -h

The buff/cache column is the page cache. available shows how much processes can actually get, taking into account that the cache will be released.

strace -T -e trace=openat,read,epoll_wait -- curl -s https://example.com -o /dev/null

-T prints the duration of each call. You can see that almost all of the program’s time is concentrated in a few waiting calls.

cat /proc/$$/io

How many bytes this process has read and written: the total (rchar) and the part that came from a real device (read_bytes). The difference between them shows the effect of the cache.

Common misconceptions

“The program is slow because it’s short on CPU.” When a process is in state S or D, the CPU has nothing to do with it. top will show a low load and a high %wa, which is the time the CPU sat idle waiting for I/O.

“The cache ate all my memory.” The page cache takes up all free memory by design and gives it back on the first request.

“epoll makes I/O asynchronous.” epoll only tells you which descriptors a read won’t block on; the read itself is still done by the program, and it is synchronous. io_uring gives you an asynchronous interface.

“More threads, faster I/O.” Threads don’t make a disk faster. Past a certain point all they add is context switches and lock contention. To wait, a descriptor in an epoll set is enough.

“DMA speeds up the transfer.” DMA doesn’t make the disk faster. It frees the CPU from shuffling bytes so it can do something useful while the transfer is in progress.

Check yourself

1. Copying a large file takes a minute, and the CPU load stays at a few percent. Why?

The kernel deliberately limits copy speedThe DMA controller moves the data; the CPU only starts the operation and gets an interrupt at the endThe file is read from the page cacheThe copy runs in a single thread

2. Why does epoll scale to tens of thousands of connections while poll does not?

epoll uses more threadsThe cost of an epoll call depends on the number of ready descriptors, not on the totalpoll does not work with socketsepoll does the reading itself

3. free shows 300 MB free out of 16 GB, the rest is in buff/cache. What does this mean?

Memory is leaking, the system needs a rebootThe memory is used by the page cache and will be released as soon as processes need it; look at the available columnThe swap file needs to be largerThe cache is misconfigured

4. How does non-blocking I/O differ from asynchronous I/O?

It doesn’t, they are synonymsNon-blocking returns EAGAIN right away if there is no data; asynchronous accepts a request and reports completion on its ownAsynchronous works only with filesNon-blocking requires a separate thread

5. Why can polling beat interrupts on very fast NVMe drives?

NVMe does not support interruptsEntering an interrupt handler and returning from it can cost more than simply waiting for the responsePolling reduces drive wearDMA does not work together with interrupts

6. A process shows state D in ps and ignores kill -9. Where should you look?

At the program’s code: there is an infinite loopAt the device the process is waiting on: uninterruptible sleep ends when the I/O operation completesAt the process schedulerAt the amount of free memory

Lab

A7: an HTTP server in three versions. First a thread per connection, then epoll, then io_uring. Measuring them under the same load shows where each model breaks. This is the most convincing part of the whole course.

B6: profiling. strace -T, perf, bpftrace: find out why a program is slow, and tell a CPU shortage apart from waiting on I/O.

Sources

• OSTEP, I/O Devices
• Silberschatz, Operating System Concepts, chapter 12
• man 7 epoll, man 2 io_uring_setup, man 5 proc
• Efficient IO with io_uring, an explanation from the author
• The C10K problem, the historical text that started the epoll era