COMS W4118 Operating Systems I

UNIX Filesystem

Refresher

• Multi-level indexed block allocation
  • I(ndex)node is the internal representation of a file, holds data block pointers and other metadata
  • Used by FFS, ext2, ext3
• Now that we understand block allocation, how do we structure our filesystem?

Motivation

• Old UNIX filesystem had poor performance
  • Expensive seeks: inodes far away from data blocks
• Design filesystem with disk geometry in mind
  • Cylinder groups: same concentric track across platters
  • Since modern devices don’t expose geometry, could also use block groups: contiguous regions of the logical block address space.
  • Keep related data within the same group to minimize seeks!

Berkeley Fast File System (FFS) Layout

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.)
• boot block(s)
  • for OS partition, place boot loader at a known place (e.g. at the very start of the partition) for the hardware to locate and execute
• cylinder group partitions
  • place inodes and data blocks into the same cylinder group to minimize disk seeks

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

---

Last updated: 2023-04-07