File Systems

Wikipedia · File system · CC BY-SA 4.0

Files and directories

A file has data (the bytes) and metadata (name, size, permissions, timestamps). A directory is a file that maps names to file references. The directory tree gives every file a unique path.

Inodes

In Unix file systems, an inode stores all metadata about a file except its name. The directory maps names to inode numbers. An inode contains pointers to the data blocks on disk. For large files, indirect pointers add extra levels of indirection.

; Simulate an inode-based file system
; Inode: (size permissions (direct-blocks ...) indirect-block)

(define (make-inode size perms direct indirect)
  (list size perms direct indirect))

(define (inode-size i) (car i))
(define (inode-direct i) (caddr i))
(define (inode-indirect i) (cadddr i))

; Directory: list of (name . inode-number)
(define root-dir '(("readme.txt" . 42) ("src" . 15) ("data.bin" . 87)))

; Inodes
(define inode-table
  (list (cons 42 (make-inode 13000 "rw-r--r--" '(8 14 23) '(31 45)))
        (cons 15 (make-inode 4096 "rwxr-xr-x" '(5) '()))
        (cons 87 (make-inode 50000 "rw-------" '(100 101 102) '(200 201 202 203)))))

(define (lookup name)
  (let ((entry (assoc name root-dir)))
    (if entry
        (let ((inode (cdr (assoc (cdr entry) inode-table))))
          (display "File: ") (display name) (newline)
          (display "  Inode: ") (display (cdr entry)) (newline)
          (display "  Size: ") (display (inode-size inode)) (newline)
          (display "  Direct blocks: ") (display (inode-direct inode)) (newline))
        (display "File not found"))))

(lookup "readme.txt")
(newline)
(lookup "data.bin")

# Inode-based file system simulation
class Inode:
    def __init__(self, size, perms, direct, indirect=None):
        self.size = size
        self.perms = perms
        self.direct = direct
        self.indirect = indirect or []

inodes = {
    42: Inode(13000, "rw-r--r--", [8, 14, 23], [31, 45]),
    15: Inode(4096, "rwxr-xr-x", [5]),
    87: Inode(50000, "rw-------", [100, 101, 102], [200, 201, 202, 203]),
}

directory = {"readme.txt": 42, "src": 15, "data.bin": 87}

def ls():
    for name, ino in directory.items():
        inode = inodes[ino]
        blocks = len(inode.direct) + len(inode.indirect)
        print(f"{inode.perms}  {inode.size:>6}  {blocks} blocks  {name}")

ls()

Allocation strategies

Contiguous: file occupies consecutive blocks. Fast reads, but causes fragmentation. Linked: each block has a pointer to the next. No fragmentation, but random access is slow. Indexed: an index block holds all pointers. Best of both, at the cost of index overhead. Unix inodes use indexed allocation with direct and indirect pointers.

Free space management

The file system tracks which blocks are free using a bitmap (one bit per block) or a free list (linked list of free blocks). Bitmaps are compact and support fast allocation of contiguous blocks.

Journaling

A journal (or log) records intended changes before applying them. If the system crashes mid-write, recovery replays or rolls back the journal. This turns a potentially corrupted file system into one that recovers in seconds instead of hours of fsck.