Understanding the Linux Kernel: The Block Layer

By Jesús Espino • • 14 min read
#Linux #Kernel #Block Layer #Storage
📚 Understanding the Linux Kernel (6 of 7) ▼
  1. 1. The Linux Kernel Startup
  2. 2. System Calls
  3. 3. Memory Manager
  4. 4. The Scheduler
  5. 5. The VFS
  6. 6. The Block Layer You are here
  7. 7. Kernel Modules
The Block Layer

In the previous article we followed a read() all the way down through the VFS: from the syscall, to the struct file, to ext4, and into the page cache. And there was exactly one moment where we skipped over the details. When the page cache missed — the bytes weren’t in memory yet — the filesystem had to actually go and fetch them, and all we said was that it “reads the disk, through the block layer.” That’s the moment we’re going to open up now.

📌 A note on scope

Everything here is against Linux 7.1. The block layer lives in block/, with its public contracts in include/linux/blk_types.h and include/linux/blk-mq.h. And as usual, this is a deliberate simplification: I’m skipping the cgroup I/O controllers, inline encryption, zoned devices and data-integrity handling, all of which hook into this same path. I’m also focusing on the read path.

The mental model: three objects between two worlds

Before we get into the details, let me hand you the mental model, because the whole block layer really is just three objects sitting between two familiar worlds. Once you have their shapes in your head, everything after this is detail.

At the top is everything that wants I/O done — the page cache taking a miss, or the VFS servicing a read()/write(). At the bottom is the device driver — NVMe, SCSI, virtio-blk — whose job is to speak the hardware’s actual language. The block layer is the negotiator in between, and it deals in three nouns:

  • The bio is a wish. “Read these 4 KiB, from this spot on the disk, into this page of memory.” It’s the unit a filesystem hands down. Every trip through the block layer begins with one.
  • The request is the device’s unit of work: one or more bios landing on adjacent stretches of disk, gathered into a single request for the hardware. (Virtual devices like LVM, software RAID or dm-crypt skip this entirely — they take bios directly and usually emit new bios for the real hardware underneath.)
  • The queues are where requests wait their turn.

We’ll explain each of these properly as we go — bio first, then request, then the queueing machinery. This is just the shape to keep in the back of your mind. Here’s how the layers stack up:

Diagram of the storage stack as four stacked layers with the block layer in the middle: at the top the world that wants I/O done (a page cache miss, VFS read/write), which submits a bio down into the block layer (blk-mq), the negotiator in between, holding its three objects in sequence — the bio (a wish: read these bytes into these pages), the request (a job on the device) and the queues (where jobs wait, one per CPU) — which then hands off a request down to the driver (NVMe, SCSI, virtio-blk), and at the bottom the device itself, flash or platter

Everything in the rest of this article is just filling in what happens at each of those arrows. Let’s start with the first of those three objects.

The bio

In the source it’s a struct bio (include/linux/blk_types.h:210) if you want to go read it, but forget the struct for a second; the interesting thing is what a bio says.

A bio is a self-contained description of one contiguous chunk of I/O to a device, and it answers four questions:

  • Which device? The specific block device this I/O is aimed at.
  • What operation? Read, write, flush, discard, and so on — plus a handful of flags that modify it (this is speculative readahead, this is high priority, don’t block on this one).
  • Where on the disk? A single starting position, expressed as a sector (512 bytes per sector).
  • Which memory? The buffers the data should be read into or written from — the device moves the bytes there itself, using DMA (direct memory access), without the CPU copying anything.

So a bio is one operation — a read, a write, a flush, … — mapping one contiguous run of disk onto possibly scattered pages in memory.

A bio also carries one thing worth keeping an eye on: a completion callback, attached by whoever built it. The block layer calls it when the I/O finishes, so it’s the return address for the whole round trip.

Put together, that’s the whole object:

Diagram of a struct bio sitting between memory and an NVMe drive, with five numbered fields: the device (/dev/nvme0n1), the operation (READ, picked out of READ, WRITE, FLUSH, DISCARD), a start sector (67489624), a list of page/len/offset memory segments, and “when done: call bi_end_io()”; the start sector points at one contiguous run of sectors on the drive, while the three memory segments point back at non-adjacent pages 0, 4 and 7 of a column of memory pages, and a blue arrow along the bottom marks that for a READ the bytes travel from the drive into those pages

In this image we can see an example of a bio: it reads a run of sectors starting at 67489624 on /dev/nvme0n1, moves the bytes (using DMA) into three pages that happen to be nowhere near each other in memory, and when it’s finished reading it calls bi_end_io().

That’s the wish. Now let’s see what the block layer turns it into.

The request

The second object is the one the driver cares about: the struct request (include/linux/blk-mq.h:105). Where a bio says “here’s some I/O I’d like,” a request says “here’s an operation this device has been asked to perform.”

Conceptually it’s the bio’s content plus three things a bio doesn’t have: which queue it belongs to, some block-layer bookkeeping state, and — the important one — a tag.

The tag is worth slowing down for, because the name gives away almost nothing about what it actually is. Requests are not allocated when you need one. Instead, the moment the driver registers, the block layer builds all of them up front — a fixed-size array of ready-made requests, and that’s all there will ever be. A tag is simply the index of a slot in that array: “tag 7” means “the request sitting in slot 7”. Alongside it sits a bitmap recording which slots are currently in use. So:

A request is a tag. Getting a request means claiming a free tag from a bitmap; freeing a request means giving the tag back.

That one design choice does three jobs at once:

  • It bounds in-flight I/O. The tag pool size is the queue depth. If every tag is taken, no more I/O can be started, period.
  • It’s the system’s fundamental back-pressure. When the pool is empty, the submitting task simply blocks until a tag frees up. (Unless the I/O is marked “don’t block,” in which case it fails fast instead of sleeping.)
  • It’s the completion ID. The tag travels down into the hardware command and comes back in the completion. When the drive says “operation 47 is done,” the block layer looks up tag 47 and instantly knows which request that was.

Here’s the whole thing in one picture:

Diagram of a request as a tag: on the left the tag pool, a strip of twelve numbered slots preallocated once when the driver registers, some ticked as taken and some free, braced with the note that pool size equals queue depth equals the maximum I/O in flight; slot 7 is highlighted and a dashed arrow labelled “a request IS a tag” leads from it to the centre, where one struct request holds tag 7, the bios it wraps, which queue it belongs to (hctx 2) and its block-layer state; on the right the device, with the tag travelling down inside the hardware command as “tag 7” and coming back the same way in the completion

There’s the pool, some slots taken and some free. Slot 7 is one of the taken ones: it holds a request with a couple of bios in it, it went down to the device as a hardware command carrying “tag 7”, and when the device is finished it comes back saying “tag 7” — which is all the block layer needs to know whose I/O just completed.

But a request rarely goes to the device the instant it’s created. Something has to hold it in the meantime.

The queues

Now the third object, and the one that gives the modern block layer its shape.

Start with the problem it solves, because you’ve seen this trick before on this blog. One queue behind one lock means every core waits its turn for it, so the more CPUs you add, the worse it gets. We’ve seen the same fix in the memory manager and in the Go scheduler : give every CPU one of its own, and there’s nothing left to contend over.

That would be the whole design, except the hardware gets a vote too. A device supports however many queues it supports — a decent NVMe drive will offer one per CPU if it can, a SATA disk offers exactly one — and those are the only places a request can genuinely be handed over. So the block layer keeps two levels of queue and maps one onto the other. The first level is one staging list per CPU, the software queues: your task submits on CPU 7, its request waits in CPU 7’s list, and no other core has any reason to touch that lock. The second level is one queue for each queue the device really has, called an hctx (hardware context) in the source, and that’s the level that feeds the driver.

The kernel doesn’t put all of those hardware queues to the same use, though. It sorts them into three flavours — default, read and poll — with the driver saying how many of its queues to devote to each one when it registers. Dedicated read queues keep latency-sensitive reads from piling up behind a flood of writeback. Poll queues are the odd ones: they’re set up with no interrupt at all, so instead of the drive interrupting the CPU when it’s finished, the submitting thread just spins and checks for the answer itself. Which sounds wasteful, until you count the cost of the alternative: on a drive that answers in a few microseconds, taking the interrupt and waking the sleeping task back up can cost more than the read itself. Everything else — writes, discards, flushes — goes to the default ones.

Which leaves one question — how does a request get from its CPU’s list to one of those? Here’s the whole arrangement, with one request’s path traced through it:

Diagram of blk-mq’s two levels of queue: on the left, CPUs 0 to 3, each feeding its own software queue (a ctx) drawn as a tray of pending requests; in the middle a “which type?” selector — polled goes to poll, reads go to read, anything else goes to default; on the right the hardware queues (hctx) grouped by type, a DEFAULT group holding hctx 0 and hctx 1, a READ group holding hctx 2 and hctx 3, and a POLL group holding hctx 4, all of them feeding the driver and the device beyond it; a blue path traces one request from CPU 2’s tray through the type selector into hctx 2 and on into the driver

Follow the blue line. A task on CPU 2 submits a read, so the request goes into CPU 2’s tray — that’s the only lock it touches. Then the one decision in the middle: what type is this? It’s a read, so it belongs in the read group, and it lands in hctx 2, which hands it to the driver.

That middle step looks like a choice but barely is one. The wiring was settled when the device was set up: each CPU’s queue is already pointed at one specific hardware queue of each flavour — this CPU’s default one, this CPU’s read one, this CPU’s poll one. So the request just asks what it is and follows the pointer that’s already sitting there. Nothing is searched for. And notice there are four CPUs and only five hardware queues in the picture: when a device has fewer queues than the machine has cores, several CPUs simply end up wired to the same one.

The answer comes back along the same wiring. When the drive has finished — the bytes moved (using DMA) straight into the pages the bio asked for — it raises an interrupt, and the completion carries the same tag that went down with the command. The block layer looks up that tag, finds the request, and calls the completion callback of every bio inside it.

I’ve been quietly assuming something in all of that, though: that requests wait in their CPU’s list in the order they arrived. That’s only true while nobody has asked for anything cleverer.

The elevator: reordering, optionally

Now the optional step. The I/O scheduler goes by its historical name, the elevator — reordering disk requests to sweep across a platter is exactly how a building elevator serves floors: not first-come-first-served, but in whatever order minimizes travel.

The thing to get straight is that an elevator brings its own queueing with it. Attach one and the per-CPU staging lists stop being used at all: requests go into the scheduler’s own structure instead, and the hardware queue asks it for the next request rather than draining the lists (blk_mq_insert_request(), block/blk-mq.c:2623). One slot, two possible occupants. So what can go in it?

The three schedulers

Linux 7.1 ships three, and they’re three different answers to “what does fairness even mean for storage?”

  • mq-deadline — nobody waits too long. It sorts by sector to minimize seeking, but gives every request a deadline so nothing gets starved: 500 ms for reads, 5 seconds for writes (block/mq-deadline.c:30).
  • kyber — hit a latency number. It barely reorders at all; it aims at a target — 2 ms for reads, 10 ms for writes (block/kyber-iosched.c:69) — and throttles whatever is making it miss. On an SSD, latency comes from work already queued inside the drive, so the useful lever isn’t order, it’s depth.
  • bfq — everybody gets their share. It shares the device out between processes, handing each a budget measured in sectors (block/bfq-iosched.c:22).

Three reasonable options — and most machines use none of them.

And usually: none at all

Here’s the twist: on an NVMe SSD, the elevator normally isn’t used at all. The default is none (block/elevator.c:729) — which isn’t “no queue”, remember, just the plain per-CPU lists doing the job with a FIFO instead of a policy.

And the reasoning holds up. A scheduler is there to hide seek costs and to stop one greedy stream of I/O starving everyone else — but flash has no seeks, and when the work is spread across several hardware queues that can all run at once, there’s much less chance of your request being stuck behind somebody else’s in the first place. Neither problem really applies any more. A scheduler isn’t free either — it’s a lock, a data structure and a decision on every single I/O, and having one forces every request through the staging step that none is allowed to skip. mq-deadline stays the default on single-queue devices, where sorting still buys something, and you can change any of this at runtime through /sys/block/<dev>/queue/scheduler.

So the elevator is really one swappable slot with four things that can go in it:

Diagram of the elevator as an optional slot: a tray of pending requests on the left feeds a dashed box labelled “THE ELEVATOR — optional, pick exactly one”, which feeds dispatch to the driver on the right, with a blue line running straight past the box annotated “our NVMe example goes straight through”; below, four cards that can fill the slot — mq-deadline (“nobody waits too long”), showing requests filed both sorted by sector and in arrival order, 500 ms reads and 5 s writes; kyber (“hit a latency number”), with its read, write, discard and other domains beside a latency gauge, 2 ms reads and 10 ms writes, throttling depth rather than order; bfq (“everybody gets their share”), giving processes A, B and C different budgets measured in sectors rather than time slices; and none (“don’t bother”), drawn in blue as a single arrow passing straight through, the default on fast multi-queue devices

For our example, let’s say /etc/hostname lives on an NVMe drive: no scheduler, so nothing stages our read anywhere — it goes straight to the driver.

That’s every piece of machinery in the block layer. Let’s see them work together.

Walking Through an Example

Let’s run the whole thing end to end — the page-cache miss for cat /etc/hostname on an NVMe-backed ext4 filesystem, picking up exactly where the VFS article handed off:

  1. The miss. The page cache has nothing covering offset 0 of /etc/hostname, so it allocates an empty page and asks ext4 to fill it.
  2. The bio. ext4 is the only one who knows where that byte physically lives, so it looks the block up and builds a bio: read 4 KiB from this sector, into this page, and call me back when it’s done. Then it hands it to the block layer.
  3. It becomes a request. Nothing adjacent to our block is already queued for this drive, so there’s nothing to merge with. The block layer takes a free tag instead — and that tag is our request.
  4. It picks its queues. Both get stamped onto the request: the list belonging to the CPU we’re running on, and the hardware queue that list is wired to. Ours is a read, so that’s the read-flavour one if the drive asked for dedicated read queues, and the default one if it didn’t.
  5. It goes straight out. NVMe runs with no scheduler, so the request never has to sit in that CPU list waiting its turn — it goes out through its hardware queue directly to the driver, which turns it into a command the drive understands. Our task goes to sleep waiting on the page.
  6. The drive does the work. Microseconds later the SSD has moved (using DMA) 4 KiB straight into our page, and it raises an interrupt quoting the tag it was given.
  7. The answer comes back. That tag finds the request, the request’s bio is finished, and the callback ext4 attached in step 2 runs: the page is marked up to date and unlocked, which wakes our task. The tag goes back in the pool. The task copies the bytes into cat’s buffer, read() returns, and the cat /etc/hostname from the last article finally has its output.

And the page stays in the cache. Run cat /etc/hostname again and step 1’s miss becomes a hit — none of the rest happens at all.

Time to tie it all together.

Summary

And that’s the block layer: it takes “these bytes aren’t in memory” and turns it into something a drive can actually be asked to do. Three objects is all it really needs.

A bio is the wish: read this run of disk into these pages, and call me back when it’s done.

A request is what the device works in. The block layer gathers neighbouring bios into one and gives it a tag — a slot in a fixed array of ready-made requests. That tag turns out to do three jobs at once: it caps how much I/O can be in flight, it makes a task wait when there are none left, and it’s the name the drive quotes back when the operation is finished.

The queues are where requests wait: one list per CPU, so no two cores fight over the same lock, feeding the queues the device really has. Attach an elevator and it takes that level over and applies a policy instead — though on an NVMe SSD, you usually don’t want one at all.

Then the drive interrupts, quotes the tag it was given, and the whole thing unwinds back to the code that was waiting.

Now that we’ve done the VFS and the block layer, let’s zoom out a bit. Underneath both of them sits the thing we kept stopping at: the driver. And drivers aren’t really a storage topic at all — the same machinery attaches a keyboard, a network card or a GPU to the kernel. How a driver announces itself, how it gets matched to a device that turns up on a bus, and how it talks to hardware without the rest of the kernel ever having to know how: that’s what the next article is about.