File systems

A disk is just a long row of numbered blocks (often 4 KB each). A file system turns them into named files in directories. FAT32, exFAT, NTFS, ext4, APFS and Btrfs are file systems.

Files and directories

A file has data and attributes: name, size, owner, permissions, and the times it was created, changed and read. Programs use it through system calls: open (which returns a small number, a file descriptor), read, write, lseek (move to a position) and close. The kernel's open-file table remembers each open file's current position.

Directories form a tree. A path from the root (/home/rahim/notes.txt) is absolute; one from the current directory (notes.txt, ../lab2) is relative. A hard link is a second name for the same file; a symbolic link is a small file holding another file's path.

Where a file's blocks go

FAT (file allocation table) is linked allocation with the links moved out of the blocks into one table at the start of the disk: fat[b] is the block after b, and a special value ends the file. The table is small enough to keep in memory, so following a chain is fast.

#include <stdio.h>

#define BLOCKS 10
#define END -1

/* fat[b] = the block after b in its file; END ends the file; 0 = free */
int fat[BLOCKS] = {0, 0, 5, END, 0, 8, 0, 0, 3, 0};

int main(void) {
    int start = 2;          /* the directory entry says where the file starts */
    int count = 0;

    printf("file blocks:");
    for (int b = start; b != END; b = fat[b]) {
        printf(" %d", b);
        count++;
    }
    printf("\n%d blocks, %d bytes with 4 KB blocks\n", count, count * 4096);
    return 0;
}

Inodes

UNIX file systems use indexed allocation. Each file has an inode with its attributes (but not its name: the name is in the directory) and pointers to its blocks:

• 12 direct pointers to data blocks,
• 1 single indirect: a block full of pointers to data blocks,
• 1 double indirect: a block of pointers to blocks of pointers,
• 1 triple indirect: one more level.

With 4 KB blocks and 4-byte pointers, one block holds 1024 pointers, so the largest file is

(12 + 1024 + 1024² + 1024³) × 4 KB ≈ 4 TB

Small files, the most common kind, are reached in one step through the direct pointers; huge files are still possible.

Free space and crashes

• A bitmap keeps one bit per block: 1 used, 0 free. Finding free blocks near each other is easy.
• Changing a file takes several writes (data, inode, bitmap, directory). A crash between them leaves the disk inconsistent. A journaling file system (ext4, NTFS) first writes what it is about to do in a journal, then does it; after a crash it replays or drops the unfinished entries instead of checking the whole disk.

Permissions

UNIX gives each file read, write and execute permission for three classes: the user who owns it, its group, and others. chmod 754 file sets them as octal digits, 4 for read, 2 for write and 1 for execute: 7 = rwx for the user, 5 = r-x for the group, 4 = r-- for others.

#include <stdio.h>

void show(int mode) {
    char text[10];
    const char letters[] = "rwx";
    for (int i = 0; i < 9; i++) {
        int bit = 8 - i;                   /* user rwx, group rwx, others rwx */
        text[i] = (mode >> bit) & 1 ? letters[i % 3] : '-';
    }
    text[9] = '\0';
    printf("%o -> %s\n", mode, text);
}

int main(void) {
    show(0754);
    show(0644);
    show(0700);
    return 0;
}

Mark lesson complete