COMS 4995 Advanced Systems Programming

UNIX Filesystem

Filesystem Hierarchy

A filesystem hierarchy is composed of disjoint filesystems grafted (i.e., mounted) onto one unified tree. Directories and files are created within a filesystem. The UNIX filesystem hierarchy starts at /, the root directory.

mount -l lists all mounted filesystems on the system. Here are a few notable entries on SPOC:

• /dev/sda1 on / type ext4 (rw,relatime,discard,errors=remount-ro) [cloudimg-rootfs]
  • The root filesystem (stored on /dev/sda1) is mounted at /. It is formatted with ext4fs.
• students241 on /mnt/disks/students241 type zfs (rw,xattr,noacl)
  • We’ve attached a storage device named students241 to SPOC to store student home directories
  • The device is mounted at /mnt/disks/students241 and is formatted with zfs.
• w4157-home on /home type zfs (rw,xattr,noacl)
  • We’ve attached a storage device named w4157 to SPOC to store teaching staff directories and other admin stuff
  • The device is mounted at /home and is formatted with zfs.

There are other kinds of mounts:

• Special in-memory psuedo-filesystems are not backed by physical storage devices, e.g., procfs, a filesystem interface for viewing kernel process information
  • proc on /proc type proc (rw,nosuid,nodev,noexec,relatime)
• Bind-mounts allow you to mount a directory within an existing filesystem onto somewhere else in the hierarchy, effectively creating a new entrypoint.
  • sudo mount --bind <existing-dir> <mount-point>

Berkeley Fast File System (FFS) Layout

Recall inode data structure, the internal representation of a file.

• Holds metadata about file on disk (size, owner, etc.)
• Inode number uniquely identifies a file within a filesystem, not the file name
• A file on disk can be broken up into several non-contiguous data blocks. Inode holds data block pointers.

The following diagram, APUE Figure 4.13, shows the layout of FFS as if it were formatted onto one partition of a storage device:

Disk drive partitions

Disk drive can be paritioned into multiple operating systems

• e.g., dual-boot Linux and Windows

Within a single OS, can also partition disk into several filesystems

• use different filesystems for different purposes
• in UNIX, all mounted filesystems are grafted into the directory hierarchy tree

File system

Occupies a disk partition. At the top-level of FFS we have:

• boot block(s)
  • data for OS boot
• super block
  • metadata about the filesystem (#blocks, #groups, block size, etc.)
• cylinder group partitions
  • place inodes and data blocks into the same cylinder group to minimize disk seeks (i.e., increase access locality)

Cylinder group

Maintains copy of the superblock and some cylinder group metadata for performance. The crucial parts of the filesystem are:

• inode bitmap
  • which inodes are used/unused
• block bitmap
  • which data blocks are used/unused
• array of inode blocks
  • stores per-file inodes
    • note that an inode uniquely identifies a file, NOT the filename – more on this later
  • #inodes is effectively the #files you can have on the filesystem
  • sizeof(inode) ~ 128B, sizeof(datablock) ~ 4KB, should be able to fit quite a few
• array of data blocks

Inodes and Data Blocks

A given inode in the inode array represents a single file

• in the diagram above, we see that the inode stores pointers to the data blocks

Directories are pretty much just “special” files – they also occupy data blocks. A directory’s data block houses directory entries:

• one dentry per file in the directory
• each dentry has the name of the file and the inode
  • notice that two different dentries can refer to the same inode – files are uniquely identified by inode number in a filesystem, not the filename!
  • we’ll see in what cases there can be different dentries that refer to the same inode: links

Given an empty directory (represented by inode 1267 below), let’s mkdir testdir:

Notice the dentries for the directory with ino 1267:

• . refers to itself
• .. refers to the parent directory
• run mkdir to create subdirectory testdir: ino 2549

Directory with ino 2549:

• . refers to itself
• .. refers to the parent directory with ino 1267

Notice how ino 1267 is referred to by:

• . within itself
• .. in the subdirectory

Notice how ino 2549 is referred to by:

• . within itself
• testdir within the parent directory

Files can have different names but refer to the same inode!

Hard Links and Symbolic Links

$ # starting off with an empty dir
$ ls -al
total 8
drwx------ 2 hans hans 4096 Apr  7 22:30 .
drwx------ 9 hans hans 4096 Apr  7 22:30 ..
$ echo howdy > f1
$ # f1 is 6 bytes: howdy + newline
$ ls -al
total 12
drwx------ 2 hans hans 4096 Apr  7 22:31 .
drwx------ 9 hans hans 4096 Apr  7 22:30 ..
-rw------- 1 hans hans    6 Apr  7 22:31 f1
$ # we can create a hard link to f1 using ln
$ ln f1 f2
$ ls -al
total 16
drwx------ 2 hans hans 4096 Apr  7 22:33 .
drwx------ 9 hans hans 4096 Apr  7 22:30 ..
-rw------- 2 hans hans    6 Apr  7 22:31 f1
-rw------- 2 hans hans    6 Apr  7 22:31 f2
$ # f2 is not a copy or shortcut, refers to the same inode as f1
$ ls -ali
total 16
1154149 drwx------ 2 hans hans 4096 Apr  7 22:33 .
1028714 drwx------ 9 hans hans 4096 Apr  7 22:30 ..
1027866 -rw------- 2 hans hans    6 Apr  7 22:31 f1
1027866 -rw------- 2 hans hans    6 Apr  7 22:31 f2
$ # let's create a dir and make a hard link to f2 in there
$ mkdir d1
$ cd d1
$ ln ../f2 f3
$ # notice f3 has the same inode number
$ # also notice link count is 3, used be 2
$ # three dentries refer to the ino 1027866
$ ls -ali
total 12
1154150 drwx------ 2 hans hans 4096 Apr  7 22:34 .
1154149 drwx------ 3 hans hans 4096 Apr  7 22:34 ..
1027866 -rw------- 3 hans hans    6 Apr  7 22:31 f3
$ # let's inspect d1 now
$ cd ..
$ ls -ali
total 20
1154149 drwx------ 3 hans hans 4096 Apr  7 22:34 .
1028714 drwx------ 9 hans hans 4096 Apr  7 22:30 ..
1154150 drwx------ 2 hans hans 4096 Apr  7 22:34 d1
1027866 -rw------- 3 hans hans    6 Apr  7 22:31 f1
1027866 -rw------- 3 hans hans    6 Apr  7 22:31 f2
$ # d1's link count is 2: the "." inside of it and "d1" from the parent dir
$ # let's try creating a hard link to d1
$ ln d1 d2
ln: d1: hard link not allowed for directory
$ # fs typically disallows users from creating hard link to dir to prevent buggy
$ # code from going into infinite traversal. hard links to dirs do exist though (. and ..)
$ # also can't create hard links to files outside fs... different inodes!
$ # 
$ # side note: link count is the reason why there is no delete() -- just `unlink()`
$ #
$ # let's mess with symlinks now:
$ ln -s f1 s1
$ ls -ali
total 20
1154149 drwx------ 3 hans hans 4096 Apr  7 22:40 .
1028714 drwx------ 9 hans hans 4096 Apr  7 22:30 ..
1154150 drwx------ 2 hans hans 4096 Apr  7 22:34 d1
1027866 -rw------- 3 hans hans    6 Apr  7 22:31 f1
1027866 -rw------- 3 hans hans    6 Apr  7 22:31 f2
1028812 lrwxrwxrwx 1 hans hans    2 Apr  7 22:40 s1 -> f1
$ # notice that symlink is a special file with different ino.
$ # file content is literally path to the targetted file
$ # can create symlinks to directories and files outside fs because this really is a shortcut 

Summary

• Symbolic link
  • Special file, designated by a bit in metdata
  • File data is name to another file
• Hard link
  • Multiple dentries point to the same file
  • All hard links are equal: no primary
  • Store link count in file metadata
  • Cannot refer to directories or files outside fs
• Bind mount
  • Just another entrypoint to an existing filesystem

---

Last updated: 2024-04-10