Simple Filesystems

Let's begin by trying to come up with the simplest and easiest way to support our low-level filesystem interface.

Fixed Partitioning

The first scheme for putting files on a disk is about as simple as we can devise. Just split the disk into preallocated fixed-size chunks. For example, we could divide the disk into four equal parts, and each file gets one of those parts. This scheme is called fixed partitioning.

Thus, we'd implement our filesystem operations as follows:

• create(): Find a free partition and return its ID (marking it as used).
• delete(fileID): Mark the partition as free.
• extend(fileID, count): Increase the space marked as used for this file; if the file size would exceed the partition size, return an error.
• size(fileID): Return the size of the used space for this file (not the partition size).
• write(fileID, blockNum, count, data): Write data to the partition for this file starting at a block number and writing a certain number of blocks, using the start of the partition as block 0.
• read(fileID, blockNum, count): Analogous to write; returns the data read.

Metadata

Metadata is data about data. In the case of a filesystem, it's information about the files on the disk. For fixed partitioning, we need to keep track of which partitions are in use and which are free, as well as how big each one is and how much of it is actually in use.

Filesystem Simulator

Our filesystem simulator will show you how the filesystem works. You can create files, write to them, and read from them. You can also see how the filesystem keeps track of the files and their sizes.

Because use of a filesystem is a bit more complex than “read a sector, write a sector,” we'll provide our own simple scripting language, SimScript, to let you automate the process of creating files, writing to them, and erasing them. It provides the following operations akin to the ones we've defined:

• create(): Create a new file and return its file ID.
• delete(fileID): Delete a file.
• extend(fileID, count): Extend a file by a certain number of blocks.
• size(fileID): Return the size of a file in blocks.
• write(fileID, blockNum, count): Write data to a file starting at a block number and writing a certain number of blocks—notice that we don't bother with the data itself.
• read(fileID, blockNum, count): Analogous to write.
• push(fileId, count): Add write blocks to the end of a file. It is exactly equivalent to let oldSize = size(fileId); extend(fileId, count); write(fileId, oldSize, count);, it's just provided for convenience.

let x = create()          // Store a file ID
let s = size(x)           // Get file size
let n = (s * 2) + 1       // Arithmetic expressions

// Sequential repetition
repeat 5 {
    let f = create()
    if (f == 0) {
        // First file we've created
        push(f, 1)
    } else {
        push(f, 2)
    }
}

// Parallel execution block
par {
    push(f1, 3)     // Each statement is executed in parallel
    push(f2, 2)
}

// Parallel repetition
par repeat 4 {      // Each iteration is executed in parallel
    let f = randint(0, maxFileID)
    push(f, 1)
}

You can explore the simulator by just clicking the Start Simulation button below. There are things to try next in the text following the simulator.

Actual Simulator

Exploring Fixed Partitioning (and the Simulator)

Once you've run the simulation once, try the following:

• Comment out the first line (using //) so that it doesn't try to create any more files.
• Run the simulation again, and it will write to the files that already exist.
• Change the second repeat to par repeat and see what happens.

Dynamic Partitioning

Both static partitioning and dynamic partitioning are approaches we first looked at when we considered how to allocate memory to programs, so it makes sense to consider both approaches for filesystems as well, even though dynamic partitioning is rarely used for filesystems in practice.

When you click the button below, the “Dynamic Partitioning” scheme will be added to the filesystem scheme drop-down, the simulator will automatically switch to use that scheme, and you'll get a new script to demonstrate it (replacing any existing script you might have made and erasing any existing filesystem state).

Click the link to go back to the simulator and try running the new script. You can also try switching to a larger disk size and fill it up with files of varying sizes. When you've experimented a bit, you can click the link under the simulator to come back here.

A big problem with these simple approaches is their requirement of contiguous allocation. While it's nice to put all the blocks of a file next to each other, insisting on it is too limiting. In practice, we need to be able to put files wherever there's space, even if it's scattered around the disk.

But before we leave this technique, it's worth noting that we can support multiple files being written at once if we preallocate space for them. So, for example, code where create now takes a size parameter and allocates that much space for the file would work.

par repeat 10 {
    let size = randint(3, 20);
    let f = create(size);
    let i = 0;
    repeat size {  // Write the file, block by block
        write(f, i, 1)
        i = i + 1;
    }
}

File Allocation Table

The File Allocation Table (FAT) is a simple and widely used technique for managing files on disk. It's used in many filesystems, including the venerable FAT16 and FAT32 filesystems typically used on floppy disks, hard drives, and USB sticks.

Rather than store the linkage between blocks in the blocks themselves, that information is stored in the FAT. Each entry in the table corresponds to a block on disk, and the value in the table tells you the location of the next block in the file. The last block in the file has a special value to indicate that it's the end of the file.

Click the button below to switch to the FAT filesystem scheme and set up a new script to demonstrate it. The provided script

• Creates five (additional) files
• Performs seven iterations of the following:
  • Adds twelve blocks total to randomly chosen files (in parallel)
  • Deletes a random file
  • Creates a new file to replace it

As usual, this example is meant to represent a plausible filesystem workload with multiple processes working on different files at the same time.

Adding Clusters

We can't actually make the blocks bigger, as they're a fixed size on the disk, but we can group blocks together to achieve the same effect. We could call them “logical blocks” but that name is taken, so instead we'll call them “clusters”. Each cluster will contain a fixed number of blocks (e.g., eight), and the FAT will point to clusters rather than individual blocks.

The effect of this change is

• The chains of blocks become chains of clusters, and become shorter.
• Within each cluster, blocks are contiguous, so reading a file is faster.
• The FAT table is smaller, as it points to clusters rather than individual blocks.

You can see this in action by clicking the button below to switch to the FAT filesystem with clusters of eight blocks each. The provided script is the same as before, but with the cluster size set to eight.

By gathering blocks into clusters, we now have the problem of internal fragmentation. If a file doesn't use all the blocks in a cluster, we can't use the remaining space for anything else.

Clusters vs. SSDs and Flash Blocks

For SSDs, the problem is even worse. As we saw in the previous lesson, SSDs have a minimum unit of erasure, called a flash block. If our filesystem isn't aligned with the flash blocks, we'll end up with clusters straddling them, which is bad for performance and longevity. We'll need to be careful about how we manage our clusters to avoid this problem. In this case, we should have started the first cluster at block 8, not block 2, to avoid this issue.

It's also important to use the trim command to tell the SSD that a block is no longer in use. This requirement reveals a subtle difference between what the filesystem should do when there is an SSD compared to a spinning disk:

• For an SSD, it's important to use trim to tell the SSD that a cluster is free. At that point, the data in the cluster is gone.
• For a spinning disk, we don't need to do anything special when we erase a file. The data is still there, but the blocks are marked as free. (Which means someone who obtains a disk with “deleted” files may still be able to recover the data. Be sure to run a secure formatting option before you throw away (or donate) a hard disk!)

Complexity and Reliability

In some ways, the FAT scheme is still quite simple, but it is nevertheless more complex than our previous schemes.

Some good rules of thumb are

• Updates to the FAT need to be atomic—only one process can be adding or removing clusters from the chains at a time.
• Updates to the FAT must precede updates to the disk blocks. Otherwise two processes might think the same block is free and write to it at the same time.

The file-allocation table itself can be quite large, and it is the only source of metadata about the filesystem. If it's corrupted, the filesystem is lost and cannot easily be reconstructed.

For this reason, it's actually common to have multiple copies of the FAT, so that if one is corrupted, the others can be used to reconstruct the filesystem. This is a simple form of redundancy that can help improve reliability.

Summary of Issues with the FAT Approach

While the FAT filesystem technique does give us a workable filesystem, as we've seen, it has some significant drawbacks. Let's summarize them:

• Internal Fragmentation: If a file doesn't use all the blocks in a cluster, the remaining space is wasted.
• File Fragmentation: Files are no longer contiguous, and blocks are scattered around the disk, which can slow down reading and writing files, particularly on spinning disks.
• Serialization: The need to update the FAT table atomically can create performance bottlenecks if multiple processes are trying to write to the disk at the same time.
• Complexity & Reliability: The FAT table is a single point of failure, and managing it correctly is complex. If the FAT table is corrupted, the filesystem is lost.
• SSD Issues: Older FAT filesystems unaware of SSDs may fail to align clusters with flash blocks or fail to use trim, leading to poor performance and faster wear.
• Space Wastage: The FAT table can be quite large, and if we make duplicates for redundancy, we're wasting even more space.

On the other hand, the FAT filesystem is simple and widely used. For something like a USB stick, where we usually just write files one at a time and often don't bother to erase them, it's a good choice. It's also a good choice for filesystems that need to be read on multiple operating systems, as it's widely supported.

Other Schemes

We won't simulate the remaining three filesystem schemes we'll look at.

In the first two, what happens at the disk level isn't much different than what we've already seen—how they differ is in how they manage the metadata about what block belongs to what file.

Indexed Allocation

In the indexed allocation scheme, each file has an index block that contains pointers to all the blocks in the file. This approach allows files to be noncontiguous, and the index block can be updated atomically. This scheme is used in the Unix File System (UFS, UFS2; from BSD and thus in many proprietary UNIXes), and Linux's ext2, ext3, and ext4 filesystems.

We can also designate some space in the index block to hold information that the higher-level filesystem might need, such as the file's size in bytes rather than blocks, access permissions, reference counts, and so on. There is one primary index block (a.k.a. index node or inode) for each numeric file ID, so there is a one-to-one correspondence between file IDs and index block numbers, or inode numbers.

Here's a diagram of what an index node looks like in UFS:

In the diagram,

• Yellow areas point directly to data blocks, so we call them direct.
• Cyan areas point to yellow areas, which point to data blocks, so they're called a single indirect.
• Green areas point to cyan areas, which point to yellow areas, which point to data blocks, so they're called a double indirect,
• Pink areas point to green areas, which point to cyan areas, which point to yellow areas, which point to data blocks, so they're called a triple indirect.

Finding the Index Block

Each index block corresponds to a numeric file ID, so one option is to do things analogously to a fixed-size array. We decide on the maximum possible number of files we'll have, and put all the index blocks in a row. Then the offset of the desired index block is just the file ID times the size of the index block, which is almost certainly just one logical disk block, so the calculation is trivial.

The key positive features of indexed allocation are

• Distributed Metadata: The metadata for each file is stored separately, rather than using one big table for the whole filesystem as FAT does.
• Completely Flexible Block Allocation: Files can be any size, and blocks can be anywhere on the disk. Although we can have clusters, we don't need them, as the multiple levels of indirection scale well.
• Supports “Sparse” Files: By leaving some direct or indirect pointers null, we can have holes in files where there is no data. This ability is handy for some applications, such as databases, where we might want to reserve space for a file but neither write to it all at once nor always write at the end. Sparse files are not a natural fit for FAT as it links together actual allocated clusters.

Extents

In the extents scheme, each file has a list of extents, where each extent is a range of contiguous blocks on the disk (as opposed to a single block). This approach allows files to be noncontiguous, but assumes they'll mostly be made from large contiguous chunks.

Implementation is very similar to indexed allocation, where we have an “inode” for each file, but instead of pointing to individual blocks, has a table of extent, where each extent is just the start block and the length. And, like indexed allocation, we have room to store a fixed number of extents in the file's inode, but if necessary we can overflow into additional blocks. Unlike indexed allocation, we don't need a complex hierarchy of indirection because the number of extents is likely to be small even when the total number of blocks in the file is large.

This scheme was used in the HFS+ filesystem that used to be used on Macs and iPhones.

Log-Structured Filesystems

In a log-structured filesystem, all changes to the filesystem are written to a log, which is periodically merged into the main filesystem. This approach can be more efficient for SSDs, as it reduces the number of writes to the same block. It's used in the ZFS and OpenZFS filesystems. Apple's newer APFS filesystem is also log-structured, relying on CoW (Copy-on-Write) to ensure that the filesystem is always consistent.

(When logged in, completion status appears here.)