A6. A file system with FUSE

advancedbuilds on module 15

Goal

Every file system comes down to a few on-disk structures: a superblock, bitmaps, an inode table, data blocks. Module 15 describes them and explains why a file’s name lives in the directory, not in the inode. In this lab you’ll implement these structures yourself, mount the result with FUSE, and check it with ordinary ls, cat, and ln. After that, hard links stop being a curiosity: a hard link is a second directory entry with the same inode number. FUSE runs in user mode, so a bug kills only your program, and the system stays up.

After this lab you will be able to:

• break a file system image down into a superblock, bitmaps, an inode table, and data blocks, and explain what each region is for;
• implement FUSE handlers so that ls, cat, mkdir, ln, and rm work with your format without any changes to those utilities;
• explain why unlink doesn’t destroy data until the link count reaches zero, and show it on your own file system with stat on two names;
• check that the file system’s state survives unmounting, and find what was kept only in memory.

On the job, this comes up when fsck checks those same counters and bitmaps after a power loss, or when you mount sshfs or cloud storage: they’re built on the same FUSE.

Task

Write two programs: mkfs.myfs, which creates an empty file system in an image file, and myfs, which mounts that image with FUSE.

./mkfs.myfs disk.img 64M     # create an empty file system in a file
./myfs disk.img /mnt/my      # mount
fusermount3 -u /mnt/my       # unmount

What it must do:

• mkfs.myfs writes the superblock, zeroes the bitmaps, and creates the root directory with . and .. entries;
• after mounting, mkdir, touch, echo > file, cat, ls -l, ln, rm, and stat work inside it;
• files read back and have the correct size in stat; a 100 KB file is written in full;
• rmdir refuses on a non-empty directory and removes an empty one;
• hard links: ln gives a second name with the same inode number and a link count of 2; after the first name is removed, the data reads through the second one, and the count becomes 1;
• blocks go back to the free pool after a file is deleted, and df on the mount point shows it (the statfs handler);
• all of the above survives unmounting and mounting again.

What you don’t need to do. Indirect blocks and a journal are moved to “Further, if you’re curious”. The automated check doesn’t use symbolic links, renaming, or permissions. Keeping an open file with zero nlink alive until it’s closed is optional, but there’s an item about it in the report.

Constraints. libfuse handles only the exchange with the kernel; path parsing, directory entries, bitmaps, and file growth you write yourself, following the format below.

What to write in the report:

• what happens in your file system if you delete a file someone has open (see the Aside after the stages);
• the maximum file size your format allows and what limits it;
• the number of free blocks before and after creating and deleting a file a hundred times;
• what didn’t survive a remount the first time and where it was kept only in memory.

Done when:

• ./check.sh ./myfs ./mkfs.myfs passes all twenty-one checks in six groups; if df doesn’t see free space, the script skips the freeing check, and twenty remain;
• an image created by mkfs.myfs mounts a second time with all files and links in place;
• the report covers the four points above.

The check hasn't been verified against a reference yet

Unlike the others, this script hasn’t yet been run against a reference solution: it needs /dev/fuse, which a container doesn’t have. If the check gets something wrong in your case, report it: the bug may be in the check.

Before you start

• Read the sections “inode”, “Block allocation”, and “overlayfs and FUSE” in module 15.
• You need the /dev/fuse device, which an unprivileged container doesn’t have (why). Use a virtual machine or WSL2. The Vagrant machine from the archive already has libfuse3-dev and fuse3; on your own system, setup/provision.sh installs them.
• Unpack the course archive: the check is in labs/a6-filesystem/check.sh. It needs fusermount3 (or fusermount) and mountpoint; it allows 10 seconds for mounting. The handlers are described in fuse3/fuse.h, in the fuse_operations structure.

On-disk format

Minimal, but real:

Region	Contents
Superblock	signature, block size, number of inodes and blocks, offsets of the other regions
Inode bitmap	one bit per inode: in use or not
Block bitmap	one bit per data block
Inode table	type, permissions, size, link count, timestamps, block pointers
Data blocks	file contents and directory entries

A directory is stored as a regular file whose contents are a sequence of entries: “name length, inode number, name”.

Stages

1. mkfs. Create the image, write the superblock, zero the bitmaps, create the root directory with . and .. entries.

2. Mounting and reading. Implement getattr, readdir, open, read. At this stage the file system is already visible in ls, even though you can’t write to it yet.

   getattr is the most important of them: nothing works without it, and it’s where people usually get stuck.

3. Writing. create, write, truncate, unlink. This is where working with the block bitmap and growing files comes in.

4. Directories. mkdir, rmdir. rmdir must refuse on a non-empty directory; make sure your check doesn’t count . and ...

5. Hard links. link increments the count, unlink decrements it; the inode is freed only at zero.

   A required check: create a file, make a link to it, delete the original, read through the second name. The data must still be there.

6. Surviving a restart. Unmount, mount again, make sure everything is in place. If not, you were keeping something only in memory.

The link count doesn't count opens

nlink counts names, not descriptors. A file with zero nlink that is still open must exist until it’s closed (module 15).

Implementing this is optional, but write in the report what happens in your file system if you delete an open file. An honest answer of “the data disappears immediately” is better than silence.

Automated check

The check is in the archive with the course files, and the commands below are run from the unpacked directory.

cd labs/a6-filesystem
./check.sh ./myfs ./mkfs.myfs

The script creates an image, mounts it in a temporary directory, runs scenarios with files, directories, and links, then unmounts and mounts again to check that the state was preserved.

Common mistakes

Hard links “don’t work” even though the code is correct. The costliest trap in this lab, and it isn’t in your code. By default libfuse substitutes its own inode numbers for the ones you return from getattr, and caches attributes for a second. So stat shows two different inodes for two names of the same file, and a stale nlink.

The fix is an init handler:

static void *fs_init(struct fuse_conn_info *conn, struct fuse_config *cfg) {
    cfg->use_ino = 1;        // take st_ino from our getattr
    cfg->attr_timeout = 0;   // don't cache attributes
    cfg->entry_timeout = 0;
    return NULL;
}

You can leave the cache on in a finished file system, but while you’re debugging it, it hides half of the bugs.

getattr returns the wrong size. Then cat reads too much or truncates the file. The size comes from the inode; the number of blocks doesn’t determine it.

A directory has no . and ... Quite a few utilities rely on them, so ls starts behaving strangely.

Blocks aren’t freed. Space leaks with every deletion. It’s easy to check: create and delete a file a hundred times, then look at the free blocks.

No bounds checking. A name longer than the maximum, or a write past the end of a file, corrupts neighboring structures. It’s the same bug as in A4, only on disk.

Further, if you’re curious

Add indirect blocks and see how the maximum file size grows (module 15). Or add a journal and check that the file system survives a crash in the middle of a write.