Cheat SheetsOperating SystemsFile Systems

File Systems — Cheat Sheet

Operating Systems · 4 topics. Download the PDF or the Instagram carousel and share it.

Cheat Sheet · AiCanCode.org
File Systems
Operating Systems4 topicsQuick revision reference
1

File System Structure & Inodes

An inode is a metadata structure that stores file attributes and pointers to data blocks; the directory system maps human-readable names to inode numbers.

  • ✓An inode stores file metadata and block pointers but NOT the filename — filenames live in directory entries.
  • ✓Directories are files too: they contain a list of (name, inode_number) pairs.
  • ✓Hard links share an inode; the file is deleted only when link count reaches zero.
  • ✓Symbolic links are separate inodes containing a path string; they can cross filesystems and can dangle.
  • ✓The superblock contains filesystem-level metadata: total inodes, total blocks, block size, free inode/block counts.
  • ✓stat <filename> in the terminal shows the inode number and all inode fields; ls -i shows inode numbers.
Java — Inode structure and max file size calculation
// Inode structure (pseudocode representation)
class Inode {
    int    fileSize;           // bytes
    short  permissions;        // rwxrwxrwx bitmask
    int    ownerId;
    int    groupId;
    long   accessTime;         // atime: last read
    long   modifyTime;         // mtime: last content write
    long   changeTime;         // ctime: last metadata change
    int    linkCount;          // number of hard links pointing here
    int    blockCount;         // number of 512-byte blocks allocated

    // Block pointers (ext2/ext3 style)
    int[]  directBlocks    = new int[12];  // 12 × 4KB = 48 KB directly
    int    singleIndirect;  // → block of 1024 pointers → 4 MB
    int    doubleIndirect;  // → block → 1024 blocks of pointers → 4 GB
    int    tripleIndirect;  // → 4 TB (rarely reached)
}

// Max file size calculation (4KB blocks, 4-byte pointers):
long blockSize    = 4096;           // 4 KB
long ptrsPerBlock = blockSize / 4;  // 1024 pointers per indirect block

long direct       = 12 * blockSize;                          //      48 KB
long singleInd    = ptrsPerBlock * blockSize;                //       4 MB
long doubleInd    = ptrsPerBlock * ptrsPerBlock * blockSize; //       4 GB
long tripleInd    = ptrsPerBlock * ptrsPerBlock * ptrsPerBlock * blockSize; // 4 TB

System.out.printf("Max file size ≈ %d TB%n",
    (direct + singleInd + doubleInd + tripleInd) / (1024L*1024*1024*1024)); // ~4 TB
2

File Allocation Methods

Filesystems use contiguous, linked, or indexed allocation to map logical file blocks to physical disk blocks, each with different trade-offs in performance, fragmentation, and random-access speed.

  • ✓Contiguous allocation gives the best sequential performance but suffers from external fragmentation.
  • ✓Linked allocation eliminates fragmentation but requires O(n) traversal for random access.
  • ✓FAT improves linked allocation by caching the entire pointer chain in an in-memory table.
  • ✓Indexed allocation (Unix inodes) provides O(1) random access and supports large files via indirect blocks.
  • ✓Modern filesystems use extents (start block + length) to reduce inode block pointer overhead for large files.
  • ✓With 4 KB blocks and 4-byte pointers, an inode with 12 direct + 1 single + 1 double + 1 triple indirect can address ~4 TB.
Java — Contiguous, linked, and FAT allocation simulation
// Contiguous Allocation simulation
// File "report.pdf" starts at block 10, length 5
class ContiguousEntry {
    String name;
    int startBlock;
    int length;
    // Access block i: disk[startBlock + i] — O(1) random access
    int blockAddress(int i) { return startBlock + i; }
}

// Linked Allocation: each block stores index of next block
int[] linkedBlocks = new int[100]; // disk blocks 0-99
// File chains: block 5 → 12 → 34 → 67 → -1 (end)
linkedBlocks[5]  = 12;
linkedBlocks[12] = 34;
linkedBlocks[34] = 67;
linkedBlocks[67] = -1; // EOF

// To read block i (0-indexed): must traverse from head — O(i)
int readLinkedBlock(int head, int i, int[] blocks) {
    int current = head;
    for (int k = 0; k < i; k++) {
        current = blocks[current];
        if (current == -1) throw new IndexOutOfBoundsException("Block " + i + " out of range");
    }
    return current;
}

// FAT (File Allocation Table): pointer table in memory, O(1) table lookup
int[] fat = new int[100]; // FAT for 100 blocks
fat[5]  = 12;  // block 5's next = 12
fat[12] = 34;
fat[34] = 67;
fat[67] = -1;  // EOF marker

// With FAT cached in memory: navigate to block i via table traversal
// Much faster than disk-based linked traversal
3

Directory Structure

Directory structures define how files are organised and named within a filesystem, evolving from flat single-level designs to hierarchical trees with sharing via links.

  • ✓Single-level directories cause naming conflicts; tree-structured directories solve this with namespacing.
  • ✓Absolute paths start from the root (/); relative paths are resolved from the current working directory.
  • ✓A directory is a file containing name-to-inode mappings — every directory has at least two entries: . (self) and .. (parent).
  • ✓Hard links create an acyclic-graph structure; cycles require garbage collection to detect unreachable files.
  • ✓Files.walk() performs a lazy depth-first traversal and must be closed (use try-with-resources) to release file handles.
  • ✓Path.normalize() is essential before security checks — /etc/passwd and /etc/../etc/passwd are the same file.
Java — Path operations with NIO
import java.nio.file.*;

// Absolute path: starts from filesystem root
Path absolute = Path.of("/home/user/projects/app/src/Main.java");
System.out.println("Root:     " + absolute.getRoot());       // /
System.out.println("Parent:   " + absolute.getParent());     // /home/user/projects/app/src
System.out.println("Filename: " + absolute.getFileName());   // Main.java
System.out.println("Parts:    " + absolute.getNameCount());  // 6

// Relative path: relative to current working directory
Path relative = Path.of("src/Main.java");
System.out.println("Is absolute: " + relative.isAbsolute()); // false

// resolve: combine a base path with another path
Path base = Path.of("/home/user/projects");
Path child = base.resolve("app/src/Main.java");
System.out.println("Resolved: " + child); // /home/user/projects/app/src/Main.java

// relativize: compute relative path from one location to another
Path from = Path.of("/home/user/projects/app");
Path to   = Path.of("/home/user/projects/lib/utils.jar");
System.out.println("Relative: " + from.relativize(to)); // ../lib/utils.jar

// normalize: remove . and .. components
Path messy = Path.of("/home/user/../user/./projects//app");
System.out.println("Normalised: " + messy.normalize()); // /home/user/projects/app

// Create directories (including missing parents)
Path newDir = Path.of("/tmp/deep/nested/dir");
Files.createDirectories(newDir); // equivalent to mkdir -p
4

Journaling File Systems

Journaling file systems use a write-ahead log to record intended changes before applying them, ensuring filesystem consistency can be recovered after a crash.

  • ✓Journaling ensures filesystem consistency after a crash by replaying committed journal entries.
  • ✓Metadata-only journaling is the default in ext3/ext4 — faster, but a crash can corrupt file data (not just metadata).
  • ✓Full journaling protects both data and metadata but roughly halves write throughput due to double-writing.
  • ✓FileChannel.force(true) in Java maps to fsync() — mandatory for durable writes in critical applications.
  • ✓Database WAL (Write-Ahead Log in PostgreSQL, InnoDB redo log) is the same concept applied at the database layer.
  • ✓Files.move() with ATOMIC_MOVE uses the OS rename() syscall — safe replacement pattern for updating config files.
Java — Journal transaction lifecycle (pseudocode)
// Journal transaction lifecycle (pseudocode)
class JournalTransaction {
    int transactionId;
    List<JournalBlock> blocks; // changed data/metadata blocks

    // Phase 1: Write changes to journal (sequential I/O — fast)
    void writeToJournal(Journal journal) {
        journal.write(new BeginMarker(transactionId));
        for (JournalBlock b : blocks) {
            journal.write(b); // write block to journal region
        }
        journal.write(new CommitMarker(transactionId));
        journal.flush(); // fsync: ensure commit hits disk before proceeding
    }

    // Phase 2: Checkpoint — write to actual filesystem locations
    void checkpoint(Filesystem fs) {
        for (JournalBlock b : blocks) {
            fs.writeBlock(b.targetLocation, b.data);
        }
        fs.flush();
        journal.freeTransaction(transactionId); // journal space reclaimed
    }
}

// Recovery on mount after crash:
void recover(Journal journal, Filesystem fs) {
    for (JournalTransaction tx : journal.committedTransactions()) {
        // Safe to replay: commit marker exists, so data is complete
        tx.checkpoint(fs);
        System.out.println("Replayed transaction: " + tx.transactionId);
    }
    for (JournalTransaction tx : journal.incompleteTransactions()) {
        // No commit marker → crash during write → discard
        journal.discard(tx);
        System.out.println("Discarded incomplete transaction: " + tx.transactionId);
    }
}
Learn this free with Aria, your AI tutor → AiCanCode.org/learn/operating-systems