Chapter 1: Hello, Disk!

The storage a device exposes is really just a long sequence of ones and zeros, with no structure or organization of its own. A filesystem takes that raw sequence and organizes it into files and directories - simple abstractions that hide all the space management happening underneath. Before we can build any of that, we need some storage, and a device-independent way to interact with it from our filesystem code. By the end of this chapter, we will have both.

We need some storage to experiment on, but not real hardware. A file works just as well - safer to play with, faster to create and discard, and if we wipe it by accident, nothing important is lost.

Luckily, creating one is straightforward on Linux. We first create an empty 4 MiB file to act as our disk, then use mkfs.fat (the standard tool for formatting FAT volumes) to write a FAT12 filesystem with the volume label MYDISK onto it (we will also set some geometry parameters here that we will explain throughout the book). Put it all in a script called create_disk.sh so we can create a fresh disk image whenever we need one:

#!/bin/bash
dd if=/dev/zero of=disk.img bs=1M count=4
mkfs.fat -F 12 -s 2 -S 512 -n MYDISK disk.img

We first need to make the script executable, then run it:

chmod +x create_disk.sh
./create_disk.sh

We should now have disk.img - a 4 MiB disk image containing a valid FAT12 filesystem. Running the command below gives us a peek at the first few bytes of what mkfs.fat actually wrote:

xxd -g 1 disk.img | head -6

00000000: eb 3c 90 6d 6b 66 73 2e 66 61 74 00 02 02 01 00  .<.mkfs.fat.....
00000010: 02 00 02 00 20 f8 0c 00 20 00 02 00 00 00 00 00  .... ... .......
00000020: 00 00 00 00 80 00 29 91 45 15 a6 4d 59 44 49 53  ......).E..MYDIS
00000030: 4b 20 20 20 20 20 46 41 54 31 32 20 20 20 0e 1f  K     FAT12   ..
00000040: be 5b 7c ac 22 c0 74 0b 56 b4 0e bb 07 00 cd 10  .[|.".t.V.......
00000050: 5e eb f0 32 e4 cd 16 cd 19 eb fe 54 68 69 73 20  ^..2.......This 

We can already see the volume label MYDISK inside it, clearly visible in the ASCII column at offset 0x002b.

A storage device does not transfer data one byte at a time - it reads and writes in fixed-size blocks called sectors. The number of bytes in each sector is device-dependent, and in practice a power of 2 (FAT itself only accepts 512, 1024, 2048, or 4096). We call this the sector size.

We passed -S 512 to mkfs.fat when formatting our disk - this set the sector size to 512 bytes. The value is recorded on the volume and must match what the device itself reports for the math to work. We will see in Chapter 2 exactly how the sector size is stored on the volume.

Every sector also has an address. We number them sequentially, starting from 0 - a scheme called Logical Block Addressing (LBA). Sector 0 is the very first block on the storage device, sector 1 is the next, all the way to the end. You can see this in the image below - the LBA is shown inside each box, and the byte offset is shown at the bottom.

Our 4 MiB disk image, with 512-byte sectors, has 8192 of them (0 through 8191):

Total sectors = Storage device size (bytes) / Sector size (bytes)
              = 4,194,304 / 512
              = 8192

Filesystem code should never talk to storage hardware directly. Instead, it defines an abstract interface - a Block Device API - that each storage driver implements. The filesystem reads and writes through that interface, never knowing or caring whether the underlying device is an ATA hard disk, an NVMe SSD, or a file on another filesystem. This is exactly what lets us swap the block device implementation without touching a single line of filesystem code - first in Chapter 12, when we move our implementation into a kernel backed by a RAM disk, then again in Appendix A, when that RAM disk gets swapped for an ATA driver.

We start by defining the interface every block device must implement:

#ifndef BLOCK_DEVICE_H
#define BLOCK_DEVICE_H

#include <stdint.h>

typedef struct BlockDevice BlockDevice;

int block_device_read(BlockDevice *device, uint64_t lba,
                      uint32_t sector_count, void *buffer);

int block_device_write(BlockDevice *device, uint64_t lba,
                       uint32_t sector_count, const void *buffer);

uint32_t block_device_sector_size(BlockDevice *device);
uint64_t block_device_sector_count(BlockDevice *device);
int block_device_close(BlockDevice *device);

#endif

Five operations make up the interface. block_device_read and block_device_write move a given number of sectors, starting at a given LBA, between the block device and a caller-supplied buffer. block_device_sector_size and block_device_sector_count report the device’s geometry - the fixed number of bytes per sector and the total number of sectors on the device. block_device_close releases whatever resources the implementation is holding.

You may have noticed something missing from the header above: block_device_close, but no matching open. That is not an oversight - opening a device needs arguments specific to whatever it actually is, so it cannot be part of the common interface. Open is the one place in this whole design where we are allowed to know exactly which implementation we are dealing with; every other operation stays behind the abstraction.

Before we implement our first block device, let’s add a little helper macro for printing debug output. We place debug prints throughout the book to trace the operations and translations our code performs, giving us insight into what is actually happening under the hood and a big help when tracking down bugs:

#ifndef DEBUG_H
#define DEBUG_H

#if DEBUG
#include <stdio.h>

#define DBG_PRINT(...)       \
    do {                     \
        printf("\033[36m");  \
        printf(__VA_ARGS__); \
        printf("\033[0m");   \
    } while (0)
#else
#define DBG_PRINT(...)
#endif

#endif

DBG_PRINT is defined conditionally, so it can be swapped out for an empty version whenever we don’t want debug prints cluttering our output. When enabled, it forwards every argument straight to printf, wrapping the message in ANSI escape codes that print it in cyan and make it stand out from our CLI’s normal output. Notice the header never defines DEBUG itself - we’ll set its value later, at compile time.

To interact with our disk image, we need a block device that reads and writes it. For that, we declare an open function that takes the path to the disk image file as its argument:

#ifndef FILE_BLOCK_DEVICE_H
#define FILE_BLOCK_DEVICE_H

#include "block_device.h"

BlockDevice *file_block_device_open(const char *path);

#endif

Then implement it:

#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include "debug.h"
#include "block_device.h"

struct BlockDevice {
    FILE *file;
    uint32_t sector_size;
    uint64_t sector_count;
};

BlockDevice *file_block_device_open(const char *path)
{
    BlockDevice *device = (BlockDevice *)malloc(sizeof(BlockDevice));

    device->file = fopen(path, "r+");
    if (device->file == NULL) {
        free(device);
        return NULL;
    }

    device->sector_size = 512;

    fseeko(device->file, 0, SEEK_END);
    device->sector_count = (uint64_t)(ftello(device->file) /
                                      device->sector_size);

    return device;
}

We first need to define what the BlockDevice struct actually holds: a file handle for the open disk image, the sector size we use, and the sector count. file_block_device_open allocates a new BlockDevice and fills in each of these. It opens the disk image file and checks whether fopen actually succeeded - if disk.img does not exist (or we lack permission to open it), fopen returns NULL, and we free the struct we just allocated and return NULL ourselves.

We hardcode the sector size to 512, since a raw file has no sector size of its own the way a real device does - but it must match the sector size we used when formatting our disk image. The sector count is computed by seeking to the end of the file to find its size in bytes and dividing by the sector size.

Now we continue with reading and writing:

int block_device_read(BlockDevice *device, uint64_t lba,
                      uint32_t sector_count, void *buffer)
{
    size_t total_bytes = sector_count * device->sector_size;
    off_t offset = lba * device->sector_size;

    DBG_PRINT("[ block_device ] read %" PRIu32
              " sector(s) at LBA %" PRIu64 " (%zu bytes at 0x%" PRIx64
              ")\n",
              sector_count, lba, total_bytes, (uint64_t)offset);

    fseeko(device->file, offset, SEEK_SET);
    fread(buffer, 1, total_bytes, device->file);

    return 0;
}

int block_device_write(BlockDevice *device, uint64_t lba,
                       uint32_t sector_count, const void *buffer)
{
    size_t total_bytes = sector_count * device->sector_size;
    off_t offset = lba * device->sector_size;

    DBG_PRINT("[ block_device ] write %" PRIu32
              " sector(s) at LBA %" PRIu64 " (%zu bytes at 0x%" PRIx64
              ")\n",
              sector_count, lba, total_bytes, (uint64_t)offset);

    fseeko(device->file, offset, SEEK_SET);
    fwrite(buffer, 1, total_bytes, device->file);

    return 0;
}

Each function translates a request expressed in LBA and sector count into a file operation expressed in byte offset and byte count. The LBA is translated into a byte offset by multiplying it with the sector size (Byte Offset = LBA * Sector Size). The sector count is translated the same way, into a byte count (Byte Count = Sector Count * Sector Size). That calculated byte offset and byte count are then used to read or write the disk image file.

The remaining three operations complete the interface:

int block_device_close(BlockDevice *device)
{
    fclose(device->file);
    free(device);

    return 0;
}

uint32_t block_device_sector_size(BlockDevice *device)
{
    return device->sector_size;
}

uint64_t block_device_sector_count(BlockDevice *device)
{
    return device->sector_count;
}

block_device_close closes the file and frees the memory of the BlockDevice struct. block_device_sector_size and block_device_sector_count just return the values we already set on open.

We have a block device and a disk image to point it at. Let’s exercise the whole interface: print its sector size and sector count, read the first sector to extract the volume label, then write a new one back.

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <inttypes.h>
#include "block_device.h"
#include "file_block_device.h"

/* same offset as in the xxd dump earlier; Chapter 2 explains why */
#define VOLUME_LABEL_OFFSET 0x2b

int main(void)
{
    /* Hardcoded so every command stays short */
    BlockDevice *device = file_block_device_open("disk.img");
    if (device == NULL) {
        fprintf(stderr, "error: could not open disk.img\n");
        return 1;
    }

    uint32_t sector_size = block_device_sector_size(device);
    printf("Sector size (bytes): %u\n", sector_size);
    printf("Sector count: %" PRIu64 "\n",
           block_device_sector_count(device));

    uint8_t sector[sector_size];
    block_device_read(device, 0, 1, sector);
    printf("Volume label: %.11s\n",
           (const char *)&sector[VOLUME_LABEL_OFFSET]);

    memcpy(&sector[VOLUME_LABEL_OFFSET], "HELLO DISK!", 11);
    block_device_write(device, 0, 1, sector);

    block_device_close(device);

    return 0;
}

Before we can actually run it, let’s add one last script that discovers every source file automatically and compiles them into one executable, which we will use throughout the rest of this book. It also reads a DEBUG environment variable and passes it straight to the compiler as a macro, so we can flip debug tracing on for a single build:

#!/bin/bash
SRC=""
for d in src platform/cli; do
    for f in "$d"/*.c; do
        [ -f "$f" ] && SRC="$SRC $f"
    done
done
gcc -Wall -Wextra -DDEBUG=${DEBUG:-0} -iquote include -iquote src -iquote platform/cli -o fat12-cli $SRC

We first need to make the script executable, then run it:

chmod +x build.sh
./build.sh

We should now have an executable named fat12-cli. Let’s run it with:

./fat12-cli

We should see the following:

Sector size (bytes): 512
Sector count: 8192
Volume label: MYDISK     

The sector count matches what we calculated earlier, and the sector size and volume label match what we set when we created the disk image. Now let’s confirm the modified volume label actually landed on our disk image too, using xxd to look at it again, the same way we did at the start of the chapter:

xxd -g 1 disk.img | head -6

00000000: eb 3c 90 6d 6b 66 73 2e 66 61 74 00 02 02 01 00  .<.mkfs.fat.....
00000010: 02 00 02 00 20 f8 0c 00 20 00 02 00 00 00 00 00  .... ... .......
00000020: 00 00 00 00 80 00 29 91 45 15 a6 48 45 4c 4c 4f  ......).E..HELLO
00000030: 20 44 49 53 4b 21 46 41 54 31 32 20 20 20 0e 1f   DISK!FAT12   ..
00000040: be 5b 7c ac 22 c0 74 0b 56 b4 0e bb 07 00 cd 10  .[|.".t.V.......
00000050: 5e eb f0 32 e4 cd 16 cd 19 eb fe 54 68 69 73 20  ^..2.......This 

HELLO DISK! sits exactly where MYDISK used to, at offset 0x002b - only those 11 bytes changed.

Let’s look at what’s happening under the hood. We create a fresh disk image and run the same code again, this time with debug output enabled:

./create_disk.sh
DEBUG=1 ./build.sh
./fat12-cli

Sector size (bytes): 512
Sector count: 8192
[ block_device ] read 1 sector(s) at LBA 0 (512 bytes at 0x0)
Volume label: MYDISK     
[ block_device ] write 1 sector(s) at LBA 0 (512 bytes at 0x0)

Now we can see each read and write request the block device receives and, in parentheses, the byte count and byte offset our file block device translated it into.

This chapter laid the foundation everything that follows depends on - a disk image with a valid FAT12 filesystem on it, and a device-independent way to talk to it from our filesystem code. Chapter 2 puts that foundation to work, introducing the boot sector - the core every filesystem operation needs.