Operating Systems Engineering and Kernel Mechanics

The boundary and what it costs

A processor runs in one of several privilege levels. On x86-64 the kernel runs in ring 0 and user code runs in ring 3. Ring 3 cannot touch a device register, cannot change a page table, and cannot mask an interrupt. Any program that wants those things must ask the kernel, and the request crosses the boundary through a system call.

A system call is not a function call. The syscall instruction switches the privilege level, switches the stack, saves the user register state, and enters a kernel entry path that sanitizes the arguments. On the way back it restores everything and switches back. The bare hardware cost is about 50 nanoseconds on a 2026 core, or roughly 180 cycles. A function call costs about 1 nanosecond.

Spectre and Meltdown made the boundary more expensive. Kernel page table isolation, or KPTI, gives the kernel and user space separate page tables, so every crossing flushes part of the TLB. Indirect branch restricted speculation and retpolines add more. With all mitigations active, a minimal system call such as getpid costs between 250 and 700 nanoseconds. That is a factor of five to fourteen over the unmitigated path.

The table explains the whole design of modern high-performance I/O. If one crossing costs 400 nanoseconds and a service handles 200,000 requests per second with four syscalls per request, the service spends 320 milliseconds of every second inside the boundary. That is 32 percent of one core, spent on nothing but transitions.

Three techniques reduce the bill. Batching amortizes one crossing over many operations, which is what io_uring does. Mapping moves the data into a shared region so that no copy and no crossing happen at all, which is what the vDSO and memory mapped files do. Moving the code into the kernel removes the crossing entirely, which is what eBPF does. The rest of this chapter covers all three.

Virtual memory as the kernel implements it

Chapter 1 described the hardware side of address translation. The kernel owns the other half. It builds the page tables, it decides which physical page backs which virtual page, and it takes the fault when no page exists.

A process address space is a set of virtual memory areas, or VMAs. Each VMA holds a range, a set of permissions, and a backing object. An anonymous VMA has no file behind it and holds the heap and the stacks. A file backed VMA maps a file, and the page cache holds its pages. Linux stores VMAs in a maple tree, which replaced the older red-black tree and cuts lookup contention.

Physical pages arrive lazily. malloc of one gigabyte returns immediately and allocates nothing. The kernel records the VMA and moves on. The first write to each page takes a page fault, and the fault handler allocates a physical page, zeroes it, and installs the page table entry. A minor fault, where the page already sits in memory, costs 500 to 2,000 nanoseconds. A major fault, where the page must come from a drive, costs 80,000 nanoseconds or more.

  user: store to 0x7f3c00001000
        |
        v
  MMU: page table entry not present  --> page fault exception
        |
        v
  kernel fault handler
        |
        +-- VMA not found ------------------> SIGSEGV
        |
        +-- anonymous, first touch ---------> allocate page, zero it,
        |                                     install PTE            (minor)
        |
        +-- file backed, page in page cache -> install PTE            (minor)
        |
        +-- file backed, page not cached ----> submit read to device,
        |                                      block the thread       (major)
        |
        +-- present but read-only, and the
            VMA allows write -----------------> copy-on-write:
                                                copy page, install RW (minor)

Copy on write makes fork cheap. The child gets the same page tables with every writable page marked read-only. A write in either process takes a fault and copies that one page. A shell that forks and immediately runs execve copies almost nothing. A language runtime that forks a 40 gigabyte heap copies pages at the rate that the two processes write them, and a garbage collector that touches every object defeats the optimization completely.

The page cache holds file data in memory. Every buffered read and write goes through it. A read that hits the cache costs a copy of about 1 to 2 microseconds for 4 KiB. A read that misses goes to the drive. Writes land in the cache, mark the page dirty, and return before any device sees the data. Writeback threads flush dirty pages later, under limits that vm.dirty_background_ratio and vm.dirty_ratio set.

When memory runs low, the kernel reclaims. It keeps pages on active and inactive lists and moves pages between them based on reference bits. Since kernel 6.1 the multi-generational LRU, or MGLRU, replaces the two list scheme with several generations and ages pages by scanning page tables rather than the pages themselves. The result is lower reclaim CPU and better choices under pressure.

Reclaim comes in two forms and only one of them is safe. The kswapd thread reclaims in the background and does not block anybody. Direct reclaim happens inside an allocating thread when kswapd cannot keep up, and it blocks that thread until pages come free. Direct reclaim is the usual cause of a service that suddenly shows 200 millisecond pauses with no change in request rate.

Scheduling: who runs next

The Linux scheduler divides tasks into scheduling classes and serves them in strict priority order. Deadline tasks run first, then real-time tasks, then normal tasks, then idle tasks. Almost all application code lands in the normal class.

The normal class used the Completely Fair Scheduler, or CFS, for fifteen years. CFS tracked virtual runtime per task and always ran the task with the smallest value. Kernel 6.6 replaced it with the Earliest Eligible Virtual Deadline First scheduler, or EEVDF. EEVDF gives every task a deadline based on its requested time slice and runs the eligible task with the earliest deadline. The change improves latency for tasks that ask for short slices and removes several heuristics that CFS needed.

Kernel 6.12 added sched_ext, which lets an eBPF program implement the scheduling policy. The kernel keeps the mechanism and hands the policy to user supplied code that loads and unloads at runtime with no reboot. A watchdog returns the system to the built-in scheduler when the eBPF scheduler stalls. Several distributions now ship sched_ext enabled, and the scx_rusty, scx_lavd, and scx_bpfland schedulers cover server, gaming, and interactive workloads.

  +--------------------------------------------------------------+
  | SCHED_DEADLINE   runtime / period / deadline, admission control|
  +--------------------------------------------------------------+
  | SCHED_FIFO, SCHED_RR   priority 1..99, no time slice for FIFO  |
  +--------------------------------------------------------------+
  | SCHED_EXT        policy supplied by an eBPF program (6.12+)    |
  +--------------------------------------------------------------+
  | SCHED_NORMAL     EEVDF since 6.6, CFS before that              |
  | SCHED_BATCH      same class, longer slices, no wake-up boost   |
  +--------------------------------------------------------------+
  | SCHED_IDLE       runs only when nothing else can               |
  +--------------------------------------------------------------+

  A single SCHED_FIFO task that never sleeps starves every SCHED_NORMAL
  task on its CPU. Use SCHED_FIFO only with a watchdog and a CPU budget.

Two scheduler behaviors cost real money in production. The first is wake-up migration. When a task wakes, the scheduler picks a CPU, and it prefers an idle one. An idle CPU on a different NUMA node costs the task its entire warm cache and its local memory. The second is time slice length. A task that runs for 1 millisecond and then blocks pays a context switch every millisecond, and each switch costs between 1 and 20 microseconds of direct cost plus the cache damage.

# Which CPU does a thread actually run on, and how often does it move?
perf sched record -- sleep 10 && perf sched latency --sort max

# Pin a latency-sensitive service to one NUMA node and disable
# wake-up migration across nodes for it.
taskset -c 0-15 ./service
echo 0 > /proc/sys/kernel/numa_balancing

# Involuntary context switches per second. A high number means that the
# task is preempted, not that it blocks.
pidstat -w -p $(pgrep -f service) 1

Control groups version 2, or cgroup v2, apply resource limits to a tree of processes. The unified hierarchy replaced the many separate hierarchies of version 1. Four controllers carry most of the weight. The cpu controller sets cpu.max as a quota and period pair, and cpu.weight as a share. The memory controller sets memory.max as a hard limit and memory.high as a throttling point. The io controller sets io.max per device. The pids controller caps the process count.

The difference between memory.high and memory.max matters more than any other cgroup detail. A cgroup that crosses memory.high gets throttled and reclaimed, and it keeps running. A cgroup that crosses memory.max triggers the out of memory killer inside that cgroup. Set memory.high about 10 percent below memory.max and the workload slows down instead of dying.

The file I/O path and the two ways through it

Buffered I/O goes through the page cache. A read copies from the cache into the user buffer. A write copies the other way and marks the page dirty. The kernel handles readahead, caching, and writeback, and the application gets good behavior with no work.

Direct I/O bypasses the page cache. open with O_DIRECT makes the kernel transfer between the device and the user buffer with no intermediate copy. The application then owns the caching decision. Databases use direct I/O because they know their access pattern better than the kernel does, and because double caching wastes memory.

Direct I/O has hard requirements. The buffer address, the file offset, and the transfer length must all align to the logical block size, which is 512 or 4096 bytes. An unaligned direct read returns EINVAL. Use posix_memalign or aligned_alloc for the buffer, and keep every offset on a block boundary.

/* Direct I/O requires alignment on all three of address, offset, length. */
#define _GNU_SOURCE
#include <fcntl.h>
#include <unistd.h>
#include <stdlib.h>

int read_block_direct(const char *path, off_t offset, void **out) {
    int fd = open(path, O_RDONLY | O_DIRECT);
    if (fd < 0) return -1;

    void *buf = NULL;
    if (posix_memalign(&buf, 4096, 4096) != 0) { close(fd); return -1; }

    ssize_t n = pread(fd, buf, 4096, offset);   /* offset % 4096 == 0 */
    close(fd);
    if (n != 4096) { free(buf); return -1; }
    *out = buf;
    return 0;
}

The choice between the two paths follows one question. Does the application know which blocks it will need again? A database with its own buffer pool knows, and direct I/O wins. A web server that serves static files does not know, and the page cache wins because it tracks the real access pattern for free. A log writer that never reads its own output wants buffered writes with periodic fsync, because the page cache absorbs bursts.

From select to epoll to io_uring

Network servers need to wait on many file descriptors at once. Three generations of interface solve that problem, and each one removes a cost that the previous one paid.

select and poll take the full descriptor set on every call. The kernel walks the whole set, and the cost grows with the number of descriptors rather than with the number of ready ones. At 10,000 connections the walk dominates.

epoll moves the set into the kernel. epoll_ctl registers a descriptor once. epoll_wait returns only the ready descriptors, so the cost tracks the number of events. This is the design that carried Linux network servers from 2002 to now, and it still carries most of them.

epoll leaves two costs. First, readiness is not completion. epoll_wait says that a socket is readable, and the program must then call read, which is a second syscall. A request that takes one read and one write costs three crossings. Second, epoll works for sockets and pipes and never worked for regular files, because a regular file is always ready.

io_uring replaces readiness with completion and replaces one syscall per operation with one syscall per batch. The kernel and the process share two ring buffers in mapped memory. The submission queue carries requests from user space to the kernel. The completion queue carries results back. Neither ring needs a system call to read or write, because both sides map the same pages.

   user space                                kernel
  +-------------------------+          +----------------------------+
  |  submission queue (SQ)  |          |                            |
  |  [ sqe ][ sqe ][ sqe ]  | -------> |  io_uring_enter() picks up  |
  |     tail ^              |          |  entries and starts the I/O |
  +-------------------------+          |                            |
                                       |  worker pool or inline      |
  +-------------------------+          |                            |
  |  completion queue (CQ)  | <------- |  posts one cqe per finished |
  |  [ cqe ][ cqe ]         |          |  operation                  |
  |     head ^              |          +----------------------------+
  +-------------------------+

  Plain mode:   one io_uring_enter() submits N operations and reaps M.
  SQPOLL mode:  a kernel thread polls the SQ. Submission costs no syscall.
  Registered buffers and files skip per-operation reference counting.
  Multishot accept/recv post many completions from one submission.

The gain is real and it is not universal. Benchmarks that submit large batches of storage I/O show io_uring reaching millions of operations per second with far fewer crossings than epoll plus read. Benchmarks that stream bulk data over a few sockets sometimes show epoll ahead, because the per-operation work dominates and epoll has a shorter path. The honest summary for 2026 has two halves. io_uring wins for storage I/O and for services with tens of thousands of concurrent connections. epoll remains a correct default for an ordinary network service.

/* Submit one read and wait for it. Real code submits many at once. */
#include <liburing.h>

int read_one(struct io_uring *ring, int fd, void *buf, unsigned len,
             off_t off) {
    struct io_uring_sqe *sqe = io_uring_get_sqe(ring);
    io_uring_prep_read(sqe, fd, buf, len, off);
    sqe->user_data = 1;

    io_uring_submit(ring);              /* one crossing for the whole batch */

    struct io_uring_cqe *cqe;
    int rc = io_uring_wait_cqe(ring, &cqe);
    if (rc < 0) return rc;
    int result = cqe->res;              /* bytes read, or -errno */
    io_uring_cqe_seen(ring, cqe);
    return result;
}

Four options change the economics further. Registered buffers pin user pages once instead of per operation. Registered files skip the descriptor table lookup. Submission queue polling puts a kernel thread on the ring so that submission costs zero syscalls, at the price of one busy core. Multishot operations post many completions from one submission, which suits accept and recv on a busy listener.

eBPF: running your code inside the kernel

The extended Berkeley Packet Filter, or eBPF, is a virtual machine inside the Linux kernel. A program in eBPF bytecode attaches to a hook, runs when the hook fires, and reports results through a map. The design solves the oldest problem in kernel extension: a kernel module can crash the machine, and an eBPF program cannot.

Safety comes from a verifier. Before it loads a program, the kernel walks every possible path through it and proves several properties. Every memory access stays inside a known object. Every loop terminates, either because it is unrolled or because it carries a bounded counter. The program finishes within an instruction budget, which is one million instructions in current kernels. A program that fails any of these tests never loads.

The verifier is strict, and the strictness is the price of running in kernel context with no memory protection. Writing eBPF means writing code that the verifier accepts, which is a smaller language than C. Compilers and libraries such as libbpf hide most of the pain. The Compile Once Run Everywhere mechanism, or CO-RE, also lets one binary run across kernel versions, because it relocates structure offsets at load time.

Maps carry state. A map is a typed key and value store that lives in the kernel and that both the eBPF program and user space can read. Hash maps, arrays, per-CPU variants, LRU variants, ring buffers, and stack trace maps cover almost every need. A per-CPU map removes the contention that a shared counter creates. User space sums the per-CPU values when it reads.

XDP deserves a separate mention because of where it runs. An XDP program runs inside the network driver, before the kernel allocates a socket buffer. It can drop, pass, redirect, or transmit a packet. Dropping in XDP costs a few tens of nanoseconds, against several microseconds for an iptables drop. A single core drops tens of millions of packets per second in XDP, which turns volume based denial of service from an outage into a line on a graph. Chapter 10 builds a container network on the same mechanism.

/* Count packets per destination port, and drop one port entirely. */
SEC("xdp")
int xdp_count_and_drop(struct xdp_md *ctx) {
    void *data     = (void *)(long)ctx->data;
    void *data_end = (void *)(long)ctx->data_end;

    struct ethhdr *eth = data;
    if ((void *)(eth + 1) > data_end) return XDP_PASS;   /* bounds check */
    if (eth->h_proto != bpf_htons(ETH_P_IP)) return XDP_PASS;

    struct iphdr *ip = (void *)(eth + 1);
    if ((void *)(ip + 1) > data_end) return XDP_PASS;
    if (ip->protocol != IPPROTO_TCP) return XDP_PASS;

    struct tcphdr *tcp = (void *)ip + ip->ihl * 4;
    if ((void *)(tcp + 1) > data_end) return XDP_PASS;

    __u16 dport = bpf_ntohs(tcp->dest);
    __u64 *count = bpf_map_lookup_elem(&port_counts, &dport);
    if (count) __sync_fetch_and_add(count, 1);

    return dport == 9999 ? XDP_DROP : XDP_PASS;
}

Every bounds test in that program exists because the verifier demands it. Omit one and the program does not load. The discipline looks heavy on a twenty line example and it pays for itself when the same code runs on every packet that reaches a production host.

Interrupts and the network receive path

A device signals the CPU with an interrupt. The CPU stops what it does, saves state, and runs an interrupt handler. Handlers must be short, because interrupts are disabled while one runs. Linux therefore splits the work. The top half acknowledges the device and schedules a softirq. The bottom half, the softirq, does the real work with interrupts enabled.

A 100 gigabit network card that raises one interrupt per packet raises about 8 million interrupts per second at small packet sizes. The machine then does nothing else. NAPI solves this. On the first packet the driver disables further receive interrupts and the kernel polls the ring. It keeps polling while packets keep arriving, and it re-enables interrupts when the ring runs dry. Under load the machine takes almost no interrupts, and under a light load it takes one per packet with the lowest latency.

Scaling across cores needs the packets spread out. Receive side scaling, or RSS, computes a hash over the packet headers in the network card and picks one of several hardware queues from it. Each queue binds to one CPU through its own interrupt. Receive packet steering, or RPS, does the same in software when the card cannot. Receive flow steering, or RFS, goes further and delivers a flow to the CPU where the application thread that owns the socket runs, which keeps the socket data in one cache.

Time, timers, and what a timestamp means

A server has several clocks and they answer different questions. CLOCK_REALTIME gives wall clock time, and it jumps when NTP steps it or when an operator changes it. CLOCK_MONOTONIC counts from an arbitrary point and never goes backward, but it does not advance during suspend. CLOCK_BOOTTIME behaves like CLOCK_MONOTONIC and includes suspend time. CLOCK_MONOTONIC_RAW skips NTP frequency adjustment.

The rule is short. Measure durations with CLOCK_MONOTONIC. Record events with CLOCK_REALTIME. A latency histogram built on CLOCK_REALTIME will show negative durations the first time NTP steps the clock backward, and the bug will appear once a month and never reproduce.

The underlying hardware source is usually the time stamp counter, or TSC. A modern TSC is invariant, which means that it ticks at a constant rate across frequency changes and across cores. The kernel picks a clock source and exposes the choice in /sys/devices/system/clocksource/clocksource0/current_clocksource. If that file says hpet or acpi_pm instead of tsc, every timestamp costs hundreds of nanoseconds instead of twenty, and the cause is usually a virtualization or firmware problem worth fixing.

Timers have a resolution and a slack. High resolution timers give nanosecond granularity in the interface and deliver with the accuracy that the hardware and the scheduler allow, which is tens of microseconds in practice. The kernel also applies a default timer slack of 50 microseconds per task so that it can group wake-ups and save power. A program that needs tighter timing sets the slack with prctl(PR_SET_TIMERSLACK, ...).

Sources and further reading

Robert Love, "Linux Kernel Development", for the structure. Brendan Gregg, "Systems Performance", second edition, and "BPF Performance Tools", for the measurement discipline and for most of the tooling in this chapter. The kernel documentation tree under Documentation/admin-guide/cgroup-v2.rst for cgroup semantics and Documentation/scheduler/sched-ext.rst for sched_ext. Jens Axboe's liburing repository and its examples for io_uring. The Cilium eBPF reference guide for the verifier and the map types.