Appendix J — How a disk is divided

Using a computer you meet these words. “Partition the disk”, “format it”, “the MBR is damaged”, “you need to convert to GPT”. You half know what they mean, and usually get by without knowing what is actually written on the disk, and how.

This appendix opens those bytes. The structures are given as tables. Their numbers were checked by examples that build the bytes to the specification and decode them again, and the page shows only the output of those checks. The code on the page comes from one program shaped like a bootloader: it reads a disk’s partition table, finds a file on a FAT partition and loads it into memory. The disks it reads were made by other people’s tools (sfdisk, mkfs.fat, QEMU), not by this book.

Words to know first#

These words are used later without explanation. There is no need to memorise them now — come back to the table.

A disk is a row of numbered cells#

What the machine knows is very simple. A disk is a row of sectors, and each sector has a number from 0. “Read sector 3”, “write these 512 bytes to sector 7” — that is effectively all the device knows.

Partitions and filesystems are laid on that row by convention. The disk does not know how it is divided.

Figure 115.1 — Three layers on one disk — the row of sectors, the partition table, the filesystem.

Places used to be named by CHS: cylinder, head, sector. Names from when a disk really was several platters. Now everything is LBA — just a number.

Why divide at all#

Can a disk not be used whole? Sometimes it can. But there are reasons to divide.

• Several operating systems together. Each uses its own filesystem.
• Separating data of different character. Swap, system, personal data. One filling up leaves the others alive.
• A separate place for booting. Like UEFI’s ESP (EFI system partition), some places must be a filesystem the firmware can read.
• A unit for recovery and backup. Imaging one partition whole, for instance.

MBR — everything written into the first 512 bytes#

The oldest scheme. One sector, sector 0 of the disk, holds both the boot code and the partition table.

★ The first and last rows tell the character of this scheme entirely. The boot code and the layout of the disk (the partition table) share the same 512 bytes. Which is why the code gets 446 bytes and there are only four partitions.

The 16-byte partition entry#

How the values pack into the three CHS bytes is worth recording too. This cramping is the source of the old limits.

== the MBR partition table (LBA 0) ==
  entry 1    bootable=yes type=0x0c (FAT32 (LBA))
             start LBA=2048 (relative) -> 2048 (absolute)  size=204800 sectors = 100.0 MiB
             CHS start=(0,32,33) end=(12,223,19)
  entry 2    bootable=no type=0x83 (Linux)
             start LBA=206848 (relative) -> 206848 (absolute)  size=2097152 sectors = 1024.0 MiB
             CHS start=(12,223,20) end=(143,106,27)
  entry 3    bootable=no type=0x82 (Linux swap)
             start LBA=2304000 (relative) -> 2304000 (absolute)  size=262144 sectors = 128.0 MiB
             CHS start=(143,106,28) end=(159,187,28)
  entry 4    bootable=no type=0x0f (extended (LBA))
             start LBA=2566144 (relative) -> 2566144 (absolute)  size=4194304 sectors = 2048.0 MiB
             CHS start=(159,187,29) end=(420,208,44)
  signature 0x55aa --- accepted as a boot sector

== the EBR chain inside the extended partition (extended start LBA=2566144) ==

  [EBR 1] absolute LBA of this EBR = 2566144
  logical    bootable=no type=0x83 (Linux)
             start LBA=2048 (relative) -> 2568192 (absolute)  size=1048576 sectors = 512.0 MiB
             CHS start=(0,32,33) end=(65,101,36)
  next EBR   bootable=no type=0x0f (extended (LBA))
             start LBA=1050624 (relative) -> 3616768 (absolute)  size=2097152 sectors = 1024.0 MiB
             CHS start=(65,101,37) end=(195,239,44)

  [EBR 2] absolute LBA of this EBR = 3616768
  logical    bootable=no type=0x07 (NTFS / exFAT)
             start LBA=2048 (relative) -> 3618816 (absolute)  size=2095104 sectors = 1023.0 MiB
             CHS start=(0,32,33) end=(130,138,8)
  next EBR   (empty)
  -> end of the chain

== the limit of what CHS can express ==
  1024 cylinders x 255 heads x 63 sectors x 512 bytes = 8422686720 bytes = 8.4 GB
  beyond that the LBA field (4 bytes) takes over: 2^32 sectors x 512 = 2.2 TB
  -> the MBR 2 TiB limit comes from here (the sector number is 32 bits).

The demonstration built exactly what the table describes and read it back. Three things to read in the output: the CHS fields, the MBR’s size limits and the type byte.

First, CHS is already abandoned. Positions too large for CHS are filled with the idiomatic FE FF FF, meaning “a position CHS cannot express”, and the reading side ignores it.

Second, the arithmetic shows where the limits come from. 1024 cylinders × 255 heads × 63 sectors × 512 bytes = 8.4 GB. And since the LBA field is four bytes, 2³² sectors × 512 bytes ≈ 2.2 TB — the MBR 2 TiB limit people speak of.

Third, the type byte is only a hint. The values in the table below are convention, “usually this”; what is really inside is known only by opening it.

The code with which a bootloader reads this table is short. Below is a piece of the demonstration run in the section “how a bootloader reads one file”. It checks the signature, moves to GPT if the first entry is 0xEE (to the alternate GPT at the end of the disk if the primary fails its checks), and otherwise walks the four entries. The bytes are assembled with le32 instead of overlaying a struct because the numbers on the disk are little-endian and do not sit on 4-byte boundaries.

int partitions(struct vblk *d, struct part *out, int max, uint64_t *gpt_at)
{
    *gpt_at = 0;
    if (vblk_read(d, 0, sec) != 0) return -2;  /* the device did not answer */
    if (sec[510] != 0x55 || sec[511] != 0xAA) return -1;  /* no signature, no MBR */
    if (sec[446 + 4] == 0xEE) {                           /* protective MBR: GPT */
        /* If the primary GPT (sector 1) fails its checks, read the backup GPT in the
           disk's last sector. The backup's entry array sits just before the backup
           header, which records where. */
        *gpt_at = 1;
        int n = gpt(d, *gpt_at, out, max);
        if (n < 0) {
            *gpt_at = d->sectors - 1;
            n = gpt(d, *gpt_at, out, max);
        }
        return n;
    }
    int n = 0;
    for (int i = 0; i < 4 && n < max; i++) {
        const uint8_t *e = sec + 446 + 16 * i;  /* four entries of 16 bytes */
        if (e[4] == 0) continue;                             /* type 0 = empty entry */
        out[n++] = (struct part){ .scheme = 'M', .mbr_type = e[4],
                                  .lba = le32(e + 8), .count = le32(e + 12) };
    }
    return n;
}

When four partitions are not enough — extended partitions and the EBR chain#

With only four entries there can be no fifth partition. The workaround devised was the extended partition. One entry is used as a marker (0x05/0x0F) saying “there are more divisions inside”, and inside the partition it describes lives a linked list.

Figure 115.2 — The EBR chain — the two entries of one EBR count from different bases.

The partitions made inside the extended partition are called logical partitions. Before each one sits one sector called an EBR (extended boot record), and only two entries of its partition table are used.

★ The third column of Table 115.7 is the trap. Two entries of the same EBR’s partition table with different bases. The latter part of the demonstration above walks that chain and computes the absolute LBAs — built deliberately, because it is the place most often misread by hand.

GPT — rebuilt out of an array, a check and a copy#

GPT (the GUID Partition Table) is the same job designed again. What changed, in one line: what was crammed into one sector was spread over an array of sectors, check values were attached so damage can be seen, and the whole thing was duplicated.

The protective MBR — sector 0 is still an MBR#

Sector 0 of a GPT disk still holds an MBR. But one partition entry, of type 0xEE, covers the whole disk. It is a decoy, to stop an old tool that does not know GPT from seeing an empty disk and overwriting it. The size field holds the whole disk (or the largest value 32 bits can express).

The 92-byte GPT header#

★ Look at offset 72. While writing this appendix it was written as 64 by mistake, which overwrote the tail of the disk GUID and made the output strange. That a mismatch between table and code shows itself is how this appendix verifies things.

The 128-byte GPT partition entry#

A GUID is written one way and stored another#

This is the first trap when reading GPT by hand.

== the GPT header (LBA 1, 92 bytes) ==
  signature        : EFI PART
  revision         : 1.0
  header size      : 92 bytes (the sector is 512; the header uses only 92)
  header CRC32     : 0x3e0d10e0
  this / alternate : LBA 1 / LBA 4194303
  usable range     : LBA 34 - 4194270
  disk GUID        : 01234567-89AB-CDEF-0123-456789ABCDEF
  entry array      : from LBA 2, 128 x 128 bytes = 32 sectors
  entry array CRC32: 0xb43cd5f9

== checking it ==
  header CRC recomputed (that field zeroed) : 0x3e0d10e0 -> matches
  entry array CRC recomputed               : 0xb43cd5f9 -> matches

== entries (128 bytes each) ==
  [1] name "EFI System"
      type GUID (as text) : C12A7328-F81F-11D2-BA4B-00A0C93EC93B
      type GUID (byte order): 28 73 2a c1 1f f8 d2 11 ba 4b 00 a0 c9 3e c9 3b 
      LBA 2048 ~ 206847  = 100.0 MiB
      attributes 0x0000000000000000
  [2] name "root"
      type GUID (as text) : 0FC63DAF-8483-4772-8E79-3D69D8477DE4
      type GUID (byte order): af 3d c6 0f 83 84 72 47 8e 79 3d 69 d8 47 7d e4 
      LBA 206848 ~ 3358719  = 1539.0 MiB
      attributes 0x0000000000000000
  [3] name "swap"
      type GUID (as text) : 0657FD6D-A4AB-43C4-84E5-0933C84B4F4F
      type GUID (byte order): 6d fd 57 06 ab a4 c4 43 84 e5 09 33 c8 4b 4f 4f 
      LBA 3358720 ~ 4194270  = 408.0 MiB
      attributes 0x8000000000000000  (bit 63 = do not automount)

== where the alternate (backup) GPT is ==
  disk 4194304 sectors = 2.0 GiB
  alternate header: the last sector, LBA 4194303
  alternate array : LBA 4194271 - 4194302 (32 sectors just before the header)
  -> damage at the front is repaired from the back, and the back from the front.

The demonstration gives evidence for three things. The header CRC is computed with that field zeroed (otherwise its own value would enter its own hash and the computation would not stand). The entry array CRC covers count × size in full — including unused slots. And the alternate GPT is at the very end of the disk, so damage at the front can be repaired from the back.

The bootloader demonstration checks GPT as below. It zeroes the header’s CRC field before computing, and computes the entry array’s CRC sector by sector while picking out the used entries. The sector number the header records for itself must match too. If anything disagrees, that header is distrusted and the alternate GPT in the disk’s last sector is read with the same checks (the branch is in the MBR piece above). On a fourth disk with one byte of the primary header damaged, the loader read the alternate and went on to the file — the primary GPT failed its checks line in the output of “how a bootloader reads one file” below.

/* CRC-32 (IEEE 802.3, reflected). One bit at a time, no table ---
   in a bootloader size is worth more than speed. */
static uint32_t crc32_update(uint32_t crc, const uint8_t *p, uint32_t n)
{
    for (uint32_t i = 0; i < n; i++) {
        crc ^= p[i];
        for (int k = 0; k < 8; k++) crc = crc >> 1 ^ (0xEDB88320u & -(crc & 1));
    }
    return crc;
}
/* … */
/* Read the GPT header at lba and the entry array it points to. */
static int gpt(struct vblk *d, uint64_t lba, struct part *out, int max)
{
    if (vblk_read(d, lba, sec) != 0) return -1;
    static const char sig[8] = { 'E', 'F', 'I', ' ', 'P', 'A', 'R', 'T' };
    for (int i = 0; i < 8; i++) if (sec[i] != (uint8_t)sig[i]) return -1;
    uint32_t hsize = le32(sec + 12);
    if (hsize < 92 || hsize > 512) return -1;
    if (le64(sec + 24) != lba) return -1;  /* its recorded own LBA must match */

    /* The header CRC is computed *with its own field set to zero*. */
    uint32_t want = le32(sec + 16);
    sec[16] = sec[17] = sec[18] = sec[19] = 0;
    if (~crc32_update(~0u, sec, hsize) != want) return -1;

    uint64_t entries_lba = le64(sec + 72);
    uint32_t count = le32(sec + 80), esize = le32(sec + 84);
    uint32_t entries_crc = le32(sec + 88);
    if (esize != 128 || count > 1024) return -1;

    /* Compute the CRC of the whole entry array sector by sector, picking out the used
       entries on the way. */
    uint32_t crc = ~0u;
    int n = 0;
    for (uint32_t s = 0; s < (count * esize + 511) / 512; s++) {
        if (vblk_read(d, entries_lba + s, sec) != 0) return -1;
        uint32_t bytes = count * esize - s * 512 < 512 ? count * esize - s * 512 : 512;
        crc = crc32_update(crc, sec, bytes);
        for (uint32_t e = 0; e < bytes; e += 128) {
            const uint8_t *p = sec + e;
            int used = 0;
            for (int k = 0; k < 16; k++) used |= p[k];  /* zero type GUID = empty */
            if (!used || n >= max) continue;
            out[n] = (struct part){ .scheme = 'G', .lba = le64(p + 32) };
            /* the ending LBA is inclusive */
            out[n].count = le64(p + 40) - out[n].lba + 1;
            for (int k = 0; k < 16; k++) out[n].guid[k] = p[k];
            n++;
        }
    }
    return ~crc == entries_crc ? n : -1;
}

Alignment — why exactly sector 2048#

Today’s tools start the first partition at LBA 2048. 2048 × 512 bytes = 1 MiB.

★ 1 MiB is a multiple of every common chunk size up to 1 MiB (each a power of two), so lining up with one lines up with all. Compare the old tools that started at sector 63 (“just past the first track” of the CHS era): 63 sectors are not a multiple of 4 KiB, so it was always misaligned.

What is inside a partition — a filesystem’s first sector#

A partition is only “from here, this many”, and what goes on inside is the filesystem’s business. A filesystem usually writes its own description into its first sector (or first block).

FAT32 — the easiest example to read#

The name FAT comes from the file allocation table this filesystem keeps near the start of the volume, and in the table below “the FAT” means that table. FAT is old and simple, which makes it a good way to learn what a filesystem must record.

== the FAT32 BPB (first sector of the partition) ==
  sector size       : 512 bytes
  cluster size      : 8 sectors = 4096 bytes (4 KiB)
  reserved sectors  : 32
  FAT copies / size : 2 x 2046 sectors
  total sectors     : 2097152 = 1024.0 MiB
  root cluster      : 2
  volume label      : "NO NAME    ", filesystem label "FAT32   "
  hidden sectors    : 2048  <- where this partition starts on the disk

== how the partition divides up ==
  reserved area : sectors 0 - 31  (boot sector, FSInfo, copies)
  FAT copy 1    : sectors 32 - 2077
  FAT copy 2    : sectors 2078 - 4123  <- a duplicate of the same content
  data area     : from sector 4124  (cluster numbers start here)
  clusters      : 261628 --- FAT32 needs at least 65525 -> it is FAT32

== changing the cluster size on the same volume ==
  cluster   clusters       one FAT      usable as FAT32
  512 B      2064606        16257 sectors yes
  1 KiB      1040400        8160 sectors yes
  2 KiB      522236         4088 sectors yes
  4 KiB      261628         2046 sectors yes
  8 KiB      130942         1024 sectors yes
  16 KiB     65503          512 sectors  no --- too few clusters
  32 KiB     32759          256 sectors  no --- too few clusters

  -> this is why a small volume ends up FAT16. Larger clusters mean fewer
     of them to manage, and the count falls below 65525.

== cluster number -> sector number ==
  formula: start of data area + (N - 2) x sectors per cluster
        (why subtract 2: 0 and 1 are used as labels and have no real place)

  cluster 2   -> sector 4124   in the partition -> absolute LBA 6172      <- the root directory
  cluster 3   -> sector 4132   in the partition -> absolute LBA 6180    
  cluster 4   -> sector 4140   in the partition -> absolute LBA 6188    
  cluster 5   -> sector 4148   in the partition -> absolute LBA 6196    

== when one file is scattered --- the FAT chain ==
  the FAT is an array of cluster number -> next cluster number (4 bytes each).
  if a file starts at cluster 3:

    cluster 3   (LBA 6180    , 4 KiB) -> next is 4
    cluster 4   (LBA 6188    , 4 KiB) -> next is 7
    cluster 7   (LBA 6212    , 4 KiB) -> end of chain

  so a file that is not contiguous can still be read. And damage to one FAT
  removes the way to find the rest of a file --- which is why there are two copies.

Three things to learn from this demonstration: the arithmetic of places, the structure of the FAT, and the cluster size.

First, the arithmetic of places is only addition. Start of the data area = reserved sectors + (number of FATs × FAT size). And the sector of cluster N = start of data area + (N − 2) × sectors per cluster. Two is subtracted because clusters 0 and 1 are reserved entries in the FAT and have no real place.

Second, the FAT is an array of “the next cluster number”. However scattered a file is across the disk, recording the next cluster’s number in each cluster lets it be read in order. So damage to the FAT removes the way to reach the rest of a file while the data is still there — which is why there are two copies.

Third, the cluster size even settles which filesystem it can be. As the demonstration’s table shows, on the same 1 GiB volume, raising the cluster to 16 KiB drops the cluster count below 65,525 and it cannot be FAT32. That is where a small USB stick formatted as FAT16 comes from.

How a bootloader reads one file#

A bootloader uses the tables so far in turn. Fetching sectors is the job of a driver for a virtio block device. virtio is the specification for the devices that virtual machines such as QEMU offer, and this driver only “reads one sector”. It touches registers only through the same four functions as the drivers in the “how machines talk” appendix, and requests and answers travel through rings kept in memory (the virtqueue). The device reads and writes those rings and the sector buffer itself, by DMA (direct memory access: a device reaching memory without the CPU).

int vblk_read(struct vblk *d, uint64_t lba, void *buf512)
{
    req = (struct req){ .type = 0, .sector = lba };
    req_status = 0xFF;
    /* header (what to read) -> data (512 bytes) -> status (1 byte), chained */
    q_desc[0] = (struct desc){ (uintptr_t)&req, sizeof req, F_NEXT, 1 };
    q_desc[1] = (struct desc){ (uintptr_t)buf512, 512, F_WRITE | F_NEXT, 2 };
    q_desc[2] = (struct desc){ (uintptr_t)&req_status, 1, F_WRITE, 0 };

    uint16_t seen = q_used.idx;
    q_avail.ring[q_avail.idx % QN] = 0;  /* one request, chained from descriptor 0 */
    /* raise idx only *after* the ring is written */
    atomic_thread_fence(memory_order_seq_cst);
    q_avail.idx++;
    atomic_thread_fence(memory_order_seq_cst);
    wr(d, Q_NOTIFY, 0);                       /* "look at queue 0" */

    /* The device answers in memory (the used ring), not in a register. */
    for (long i = 0; i < 10000000; i++) {
        if (*(volatile uint16_t *)&q_used.idx != seen) {
            atomic_thread_fence(memory_order_seq_cst);
            wr(d, INT_ACK, rd(d, INT_STATUS));
            return req_status == 0 ? 0 : -1;
        }
    }
    return -2;                                /* no answer */
}

On top of it sits the code that reads FAT: it works out the places from the BPB, settles the FAT type, and looks for the name in the root directory. A FAT12 entry is a byte and a half, so two entries share three bytes and one entry can straddle a sector boundary of the FAT. The name looked for, boot-kernel.bin, does not fit the 8.3 form (eight characters of name, three of extension), so the tool that put the file there added long-name (LFN, long file name) entries along with a short name (BOOT-K~1.BIN or similar). A long name is stored in reverse as 32-byte pieces right before the short-name entry, and every piece carries the short name’s checksum to point at its partner.

int fat_mount(struct fat *fs, struct vblk *d, uint32_t part_lba)
{
    if (vblk_read(d, part_lba, sec) != 0) return -1;
    if (le16(sec + 11) != 512 || sec[13] == 0 || sec[510] != 0x55 || sec[511] != 0xAA)
        return -1;
    uint16_t reserved = le16(sec + 14);
    uint8_t  nfats    = sec[16];
    uint16_t rootents = le16(sec + 17);                     /* 0 on FAT32 */
    uint32_t fatsz    = le16(sec + 22) ? le16(sec + 22) : le32(sec + 36);
    uint32_t total    = le16(sec + 19) ? le16(sec + 19) : le32(sec + 32);
    uint32_t rootsecs = (rootents * 32u + 511) / 512;

    *fs = (struct fat){ .disk = d, .spc = sec[13], .root_sectors = rootsecs };
    fs->fat_lba  = part_lba + reserved;
    fs->root_lba = fs->fat_lba + nfats * fatsz;             /* right after the FATs */
    fs->data_lba = fs->root_lba + rootsecs;  /* the same place on FAT32 */
    fs->clusters = (total - (reserved + nfats * fatsz + rootsecs)) / fs->spc;

    /* The FAT type is decided by the cluster count, not by the label ("FAT16   ") (the
       specification's rule). */
    fs->bits = fs->clusters < 4085 ? 12 : fs->clusters < 65525 ? 16 : 32;
    if (fs->bits == 32) fs->root_cluster = le32(sec + 44);
    return 0;
}
/* … */
/* The FAT is an array that says "after this cluster comes number ...". An entry is
   a byte and a half on FAT12, 2 bytes on FAT16, 4 bytes on FAT32 (top 4 bits unused).
   The end mark is returned as 0x0FFFFFFF for all three. */
static uint32_t next_cluster(struct fat *fs, uint32_t c)
{
    uint32_t at = fs->bits == 12 ? c + c / 2 : c * (fs->bits / 8);
    if (vblk_read(fs->disk, fs->fat_lba + at / 512, sec) != 0) return 0x0FFFFFFF;
    if (fs->bits == 12) {
        /* Two 12-bit entries share 3 bytes, so one entry can straddle a sector
           boundary. */
        uint32_t v = sec[at % 512];
        uint32_t next = fs->fat_lba + at / 512 + 1;
        if (at % 512 == 511 && vblk_read(fs->disk, next, sec) != 0) return 0x0FFFFFFF;
        v |= (uint32_t)sec[(at + 1) % 512] << 8;
        v = c & 1 ? v >> 4 : v & 0xFFF;  /* odd numbers take the top 12 bits */
        return v >= 0xFF8 ? 0x0FFFFFFF : v;
    }
    if (fs->bits == 16) {
        uint16_t v = le16(sec + at % 512);
        return v >= 0xFFF8 ? 0x0FFFFFFF : v;
    }
    return le32(sec + at % 512) & 0x0FFFFFFF;
}

static uint32_t cluster_lba(const struct fat *fs, uint32_t c)
{ return fs->data_lba + (c - 2) * fs->spc; }  /* cluster numbers start at 2 */
/* … */
/* A long name (LFN) is pieces stored in reverse *before* the short-name entry. Each
   piece holds 13 UCS-2 characters, a sequence number (0x40 on the last piece) and the
   checksum of the short name it belongs to. Pieces can cross directory sectors, so the
   state lives outside a sector. */
struct lfn { char name[261]; uint8_t sum; int valid; };

static void lfn_piece(struct lfn *l, const uint8_t *e)
{
    static const uint8_t at[13] = { 1, 3, 5, 7, 9, 14, 16, 18, 20, 22, 24, 28, 30 };
    unsigned ord = e[0] & 0x1F;
    if (e[0] & 0x40) {                                  /* the last piece comes first */
        l->valid = ord >= 1 && ord <= 20;
        l->sum = e[13];
        if (l->valid) l->name[ord * 13] = '\0';
    }
    if (!l->valid || e[13] != l->sum || ord < 1 || ord > 20) { l->valid = 0; return; }
    for (unsigned k = 0; k < 13; k++) {
        uint16_t ch = le16(e + at[k]);
        char *p = &l->name[(ord - 1) * 13 + k];
        if (ch == 0x0000) *p = '\0';                   /* end of the name */
        else if (ch != 0xFFFF) *p = ch < 0x80 ? (char)ch : '?';  /* 0xFFFF is padding */
    }
}

/* Checksum of the 11-byte short name: rotate right by one bit and add, repeatedly. */
static uint8_t short_sum(const uint8_t *e)
{
    uint8_t sum = 0;
    for (int k = 0; k < 11; k++) sum = (uint8_t)(((sum & 1) << 7) + (sum >> 1) + e[k]);
    return sum;
}
/* … */
/* The root directory: on FAT12 and FAT16 a fixed area after the FATs,
   on FAT32 a cluster chain like any file. */
static int find(struct fat *fs, const char *name, struct hit *h)
{
    struct lfn l;                   /* = { 0 } would call memset (no libc) */
    l.valid = 0;
    int r = 0;
    if (fs->bits != 32)
        for (uint32_t s = 0; s < fs->root_sectors && r == 0; s++)
            r = scan(fs, fs->root_lba + s, name, &l, h);
    else
        for (uint32_t c = fs->root_cluster; !is_end(c) && r == 0;
             c = next_cluster(fs, c))
            for (uint32_t s = 0; s < fs->spc && r == 0; s++)
                r = scan(fs, cluster_lba(fs, c) + s, name, &l, h);
    return r == 1 ? 0 : -1;
}

== this machine: the commands the driver sends (trace backend) ==
R  0x10001000 -> 0x00000000
R  0x10002000 -> 0x00000000
   ... 5 more like this, every 0x1000, up to 0x10007000
R  0x10008000 -> 0x74726976
R  0x10008004 -> 0x00000002
R  0x10008008 -> 0x00000002
W  0x10008070 <- 0x00000000
W  0x10008070 <- 0x00000001
W  0x10008070 <- 0x00000003
W  0x10008014 <- 0x00000001
R  0x10008010 -> 0x00000001
W  0x10008024 <- 0x00000000
W  0x10008020 <- 0x00000000
W  0x10008024 <- 0x00000001
W  0x10008020 <- 0x00000001
W  0x10008070 <- 0x0000000b
R  0x10008070 -> 0x0000000b
W  0x10008030 <- 0x00000000
R  0x10008034 -> 0x00000100
W  0x10008038 <- 0x00000004
W  0x10008080 <- 0x005064c0
W  0x10008084 <- 0x00000000
W  0x10008090 <- 0x005064a8
W  0x10008094 <- 0x00000000
W  0x100080a0 <- 0x00506480
W  0x100080a4 <- 0x00000000
W  0x10008044 <- 0x00000001
W  0x10008070 <- 0x0000000f
R  0x10008100 -> 0x00020000
R  0x10008104 -> 0x00000000
#  virtio-blk at 0x10008000, 131072 sectors
W  0x10008050 <- 0x00000000
#    sector 0: the device did not answer
W  0x00100000 <- 0x00005555

== QEMU virt (emulated RISC-V): the same loader on five virtio disks ==
virtio-blk at 0x10004000, 8192 sectors
  MBR partition 1: sectors 2048 + 6144, type 0x01
    FAT12: 1525 clusters of 4 sectors, FAT at sector 2049, data at sector 2091
    boot-kernel.bin, 770042 bytes: hello from sfdisk + mkfs.fat (MBR, FAT12)
    110000 numbered lines, all in order
virtio-blk at 0x10005000, 131072 sectors
  primary GPT failed its checks; using the backup at sector 131071
  GPT partition 1: sectors 2048 + 126976, type c12a7328-f81f-11d2-ba4b-00a0c93ec93b
    FAT32: 127006 clusters of 1 sectors, FAT at sector 2080, data at sector 4066
    boot-kernel.bin, 770042 bytes: hello from sfdisk + mkfs.fat (GPT, FAT32)
    110000 numbered lines, all in order
virtio-blk at 0x10006000, 131072 sectors
  GPT partition 1: sectors 2048 + 126976, type c12a7328-f81f-11d2-ba4b-00a0c93ec93b
    FAT32: 127006 clusters of 1 sectors, FAT at sector 2080, data at sector 4066
    boot-kernel.bin, 770042 bytes: hello from sfdisk + mkfs.fat (GPT, FAT32)
    110000 numbered lines, all in order
virtio-blk at 0x10007000, 131072 sectors
  MBR partition 1: sectors 2048 + 129024, type 0x0c
    FAT32: 127006 clusters of 1 sectors, FAT at sector 2080, data at sector 4066
    boot-kernel.bin, 770042 bytes: hello from sfdisk + mkfs.fat (MBR, FAT32)
    110000 numbered lines, all in order
virtio-blk at 0x10008000, 1032192 sectors
  MBR partition 1: sectors 63 + 1032129, type 0x06
    FAT16: 64474 clusters of 16 sectors, FAT at sector 64, data at sector 600
    boot-kernel.bin, 770035 bytes: hello from QEMU vvfat (MBR, FAT16)
    110000 numbered lines, all in order

The QEMU half found boot-kernel.bin by its long name on all five disks and read it. The three made by sfdisk and mkfs.fat are GPT with FAT32, MBR with FAT32 and MBR with FAT12. The fourth is a copy of the GPT disk with its primary header damaged, and was read through the alternate GPT. The remaining one, made by QEMU’s vvfat (a feature that shows a directory as a FAT disk), is MBR with FAT16. The file is about 750 KiB of 110,000 numbered lines, so one wrong step along the cluster chain breaks the numbering; on all five the numbers ran to the end. On the FAT12 disk the chain runs over 376 clusters, past the entry that straddles a sector boundary (cluster 341); built without the lines that handle that boundary, the chain broke on that disk alone.

This driver settles the FAT type not by the label but by the cluster count, the rule of the third point above — 1,525 is below 4,085 and so FAT12, 64,474 is below 65,525 and so FAT16, and 127,006 is FAT32. Asked for FAT32, vvfat still produced a FAT16 boot sector (QEMU itself warns that “FAT32 has not been tested”), so the vvfat disk was left as FAT16.

This machine’s half stops after asking for sector 0. Setting up the rings and writing Q_NOTIFY are register commands and get printed, but the sector contents are written into memory by the device through DMA, which a reply table cannot imitate. The ring addresses written to 0x10008080 and its neighbours in the output are where the program’s variables sit on this machine. Also, QEMU’s virt model is a machine on which DMA and caches do not disagree (dma-coherent), so this driver has no cache-flushing code. On a machine that is not, the cache handling listed in the DMA section of the “how machines talk” appendix is needed as well.

How ext4 and NTFS differ from FAT#

Where FAT is “an array of next-slot numbers”, ext4 centres on the inode. One file holds one inode, in which its size, permissions, times and where its data is are recorded. And places are recorded not one number at a time but as extents (contiguous runs), so a large file is described compactly.

In NTFS everything is a file — even the list of files ($MFT) is a file, and the boot sector is a file called $Boot. Record only where that list is in the boot sector, and everything else is found by following the list.

★ The “journal” column is where these filesystems differ most in practice. The FAT family, with no journal, can be left with the filesystem itself inconsistent if power is lost during a write. That is why you should use “safely remove” before pulling out a USB stick.

The physics of the medium — why random writes are slow#

So far we have read the structures written on the disk (partition tables and filesystems’ first sectors). Now the thing underneath, where the bytes actually live. The same word “storage” covers a spinning platter and a semiconductor, and their characters differ enormously — a difference that settles the design of filesystems and databases.

The spinning platter — the time to reach a place#

The time for one read on a hard disk divides into three parts.

★ The first two are the cost of finding a place and the third is the cost of the work, and the first two are about a hundred times the third. That is where “random access is slow” comes from — reading 4 KiB or 1 MiB, the cost of finding the place once is the same.

The semiconductor — writing and erasing in different units#

An SSD has no moving parts, so there is no seek. In its place another property appears: it cannot be overwritten where it stands.

Figure 115.3 — An SSD’s pages and blocks — where write amplification comes from.

Every property of an SSD follows from this.

What was measured on this machine#

fd = open(path, O_WRONLY);
double s[9];
for (int r = 0; r < 9; r++) {
    t0 = ns();
    for (int i = 0; i < 20; i++) {
        if (write(fd, buf, BLK) != (ssize_t)BLK) { perror("write"); return 1; }
        fsync(fd);
    }
    t1 = ns();
    s[r] = (t1 - t0) / 20.0 / 1e6;         /* milliseconds per fsync */
}
qsort(s, 9, sizeof *s, cmp_d);
/* … */
for (int cold = 0; cold < 2; cold++) {
    if (cold) posix_fadvise(fd, 0, 0, POSIX_FADV_DONTNEED);   /* drop only this file's cache */
    lseek(fd, 0, SEEK_SET);
    t0 = ns();
    for (unsigned i = 0; i < FILE_MiB; i++)
        if (read(fd, buf, MiB) != (ssize_t)MiB) { perror("read"); return 1; }
    t1 = ns();
    double mbs = FILE_MiB / ((t1 - t0) / 1e9);
    if (cold) seq_cold = mbs; else seq_cached = mbs;
}

== what is being measured ==
  measured with one 64 MiB temporary file. This is not the figure of one device
  but of the filesystem, the cache and the device together --- the whole stack.

== 1. sequential writing ==
  writing 64 MiB (into cache) :   6444.6 MiB/s
  one fsync after it          :     41.6 ms  <- this much had not reached the disk
  4 KiB write + fsync         :    0.319 ms each -> about 3133 per second
  * that is the cost of one database commit. Which is why designs gather several
    commits and flush them together (group commit).

== 2. reading --- with the cache, and after asking to drop it ==
  sequential read (cached)  :  10442.7 MiB/s
  sequential read (dropped) :  11043.0 MiB/s  -> a factor of 0.9
  random 4 KiB (cached)     :      2.8 us each -> 356261 per second
  random 4 KiB (dropped)    :      2.7 us each -> 369139 per second

  * the two are nearly equal --- the request to drop the cache was not honoured.
    This filesystem keeps its own cache, which `posix_fadvise` does not
    empty. So read the numbers above not as the speed of the device but as
    the speed of reading a file that is already in memory.
    (11043 MiB/s is the speed of memory, not of storage.)
    Really measuring the device needs bypassing the cache (O_DIRECT) or the
    privilege to drop the system cache, and this environment has neither ---
    so what could not be measured is left unmeasured.

== 3. placed on the ladder from earlier ==
  what                                   each against L1 (1.4 ns)
  L1 cache read                        1.4 ns            1 x
  main memory read                    75.0 ns           54 x
  random 4 KiB (from cache)            2.8 us         2005 x
  4 KiB write + fsync                319.2 us       227992 x

  * the ladder does not end at the cache. Several more orders of magnitude lie below.
    And on those lower rungs, reading in order matters far more.

★ The most important thing in this measurement’s conclusion is not what was measured but what was not. The request to drop the cache (posix_fadvise) is not honoured by this filesystem, so “sequential read” came out at 11 GiB/s — which is the speed of memory, not of storage. The demonstration checks that itself and says so.

fsync — the cost no cache can hide#

A write usually reaches only the cache. Lose power and it is gone. To be promised “it really is stored” you must call fsync, and that costs orders of magnitude more than a write that stops at the cache.

★ The last row explains database design entirely. At 0.3 ms per commit, three thousand per second is the ceiling. So databases gather several commits and flush them together (group commit), and write first to a log that is only ever appended sequentially (WAL).

What breaks where#

The symptom alone can tell which layer was damaged. That is this appendix’s practical use.

What to take from this#