High-Level Filesystem: Directories and Links

The high-level filesystem layer understands (and implements) concepts such as filenames, directories, and permissions. It allows files to be of arbitrary length in bytes, and allows reading and writing starting from any offset in a file.

This layer is what most users interact with when they use a computer.

Low-Level Filesystem Operations

In the previous lesson, we built a low-level filesystem layer that provided the following operations:

• create(): Find a free partition and return its ID (marking it as used).
• delete(fileID): Mark the partition as free.
• extend(fileID, count): Increase the space marked as used for this file; if the file size would exceed the partition size, return an error.
• size(fileID): Return the size of the used space for this file (not the partition size).
• write(fileID, blockNum, count, data): Write data to the partition for this file starting at a block number and writing a certain number of blocks, using the start of the partition as block 0.
• read(fileID, blockNum, count): Analogous to write; returns the data read.

At the end of the lesson, we added support for reading and writing metadata:

• write_metadata(fileID, metadata): Write metadata for the file.
• read_metadata(fileID): Read metadata for the file.

The low-level filesystem doesn't know or care what the metadata is; it just stores and retrieves it. Typically, such an interface limits the size of the metadata to a fraction of a block, storing it in the file's index node or the equivalent, what we usually call the inode whether it is technically an index node or not. But that is usually sufficient.

Common Metadata

Over the course of this lesson, we'll add to the things we might want to store in the metadata. For now, we'll just note that the metadata might include:

• The size of the file in bytes (the low-level filesystem only knows about blocks, not bytes).
• The file's creation time.
• The file's modification time.
• The file's last-access time.

Directories

The job of a directory is to map names to file IDs. Because the file itself holds all the other metadata, the directory is literally just a simple table, like

(These are the actual file IDs for the files in this lesson on my computer.)

A common convention is to store the (main) directory at a known file ID, like 0. Then we can read and write the directory just like any other file. On a Mac or your favorite Linux system, you can run

unix% ls -lid /
2 drwxr-xr-x  20 root  wheel  640 Nov 14 20:59 //

The number in the leftmost column (2) is the file ID for the root directory. You can see that it has file-ID 2. Presumably file-IDs 0 and 1 are reserved for other purposes.

Directory Hierarchies

Early computer systems had so little storage that it was acceptable to put all the files in a single directory. But as storage grew, the demand grew, and it became necessary to organize files into directories. Because directories are just files themselves, we can put directories inside directories, allowing us to construct a directory hierarchy.

The directory above the directory containing the files for this lesson looks like

Although it's technically not necessary, by convention, a directory contains an entry for .., which is the parent directory. This entry makes it easier to navigate the directory hierarchy without needing to start at the top and work down every time we want to move up.

Hard Links

In Unix-like systems, a file can appear in multiple directories at once. This is called a hard link. The file itself is only stored once, but it has multiple directory entries pointing to it. The high-level filesystem adds a reference-count entry to the file's metadata, and uses it to track how many directory entries point to a file, and only deletes the file when the last directory entry is removed.

Here's an example shell session as a demonstration:

[melissa@cs134-server ~]$ mkdir testdir
[melissa@cs134-server ~]$ cd testdir
[melissa@cs134-server ~/testdir]$ echo "Foo" > foo.txt
[melissa@cs134-server ~/testdir]$ echo "Bar" > bar.txt
[melissa@cs134-server ~/testdir]$ cp foo.txt xyzzy.txt
[melissa@cs134-server ~/testdir]$ ln bar.txt baz.txt
[melissa@cs134-server ~/testdir]$ ls -li
total 16
9967445 -rw-rw-r-- 2 melissa melissa 4 Dec  6 15:04 bar.txt
9967445 -rw-rw-r-- 2 melissa melissa 4 Dec  6 15:04 baz.txt
9967444 -rw-rw-r-- 1 melissa melissa 4 Dec  6 15:04 foo.txt
9967503 -rw-rw-r-- 1 melissa melissa 4 Dec  6 15:05 xyzzy.txt
[melissa@cs134-server ~/testdir]$

We used the cp command to make a copy of foo.txt called xyzzy.txt, and the ln command to create a hard link from bar.txt to baz.txt. The -i option to ls shows the file IDs, and the -l option shows other more commonly used information, like last modification time and permissions.

Here we can see that bar.txt and baz.txt have the same file ID (9967445), and foo.txt and xyzzy.txt have different file IDs. You might also notice that after the permissions (-rw-rw-r--), there is a number: 2 for bar.txt and baz.txt, and 1 for foo.txt and xyzzy.txt—that number is the reference count.

If we change the files, we can see that the changes are reflected in both files with the same file ID:

[melissa@cs134-server ~/testdir]$ echo "More Foo" >> foo.txt
[melissa@cs134-server ~/testdir]$ echo "More Bar" >> bar.txt
[melissa@cs134-server ~/testdir]$ head *.txt
==> bar.txt <==
Bar
More Bar

==> baz.txt <==
Bar
More Bar

==> foo.txt <==
Foo
More Foo

==> xyzzy.txt <==
Foo

Symbolic Links

The solution to this problem is the symbolic link (akin to shortcuts in Windows). A symbolic link is a type of special file (DT_LNK) that contains the name of another file. When you open a symbolic link, the system reads the name of the file it points to and opens that file instead.

Here's a continuation of our example session:

[melissa@cs134-server ~/testdir]$ ln -s foo.txt qux.txt
[melissa@cs134-server ~/testdir]$ ln -s qux.txt quux.txt
[melissa@cs134-server ~/testdir]$ ls -li
total 16
9967445 -rw-rw-r-- 2 melissa melissa 13 Dec  6 15:07 bar.txt
9967445 -rw-rw-r-- 2 melissa melissa 13 Dec  6 15:07 baz.txt
9967444 -rw-rw-r-- 1 melissa melissa 13 Dec  6 15:07 foo.txt
9981746 lrwxrwxrwx 1 melissa melissa  7 Dec  6 15:23 quux.txt -> qux.txt
9981729 lrwxrwxrwx 1 melissa melissa  7 Dec  6 15:23 qux.txt -> foo.txt
9967503 -rw-rw-r-- 1 melissa melissa  4 Dec  6 15:05 xyzzy.txt

Here, we can see that qux.txt and quux.txt are symbolic links to foo.txt. The l at the beginning of the permissions string indicates that they are symbolic links, and the -> in the listing shows what they point to. Here they're pointing to files in the same directory, but they can point to files anywhere on the filesystem, using either absolute paths (starting with /) or relative paths (e.g., ../othertest/foo.txt).

Let's write to the symbolically linked files and see what happens:

[melissa@cs134-server ~/testdir]$ echo "Extended Quux" >>quux.txt
[melissa@cs134-server ~/testdir]$ head *.txt
==> bar.txt <==
Bar
More Bar

==> baz.txt <==
Bar
More Bar

==> foo.txt <==
Foo
More Foo
Extended Quux

==> quux.txt <==
Foo
More Foo
Extended Quux

==> qux.txt <==
Foo
More Foo
Extended Quux

==> xyzzy.txt <==
Foo
[melissa@cs134-server ~/testdir]$ echo "Overwrote Qux" >qux.txt
[melissa@cs134-server ~/testdir]$ head *.txt
==> bar.txt <==
Bar
More Bar

==> baz.txt <==
Bar
More Bar

==> foo.txt <==
Overwrote Qux

==> quux.txt <==
Overwrote Qux

==> qux.txt <==
Overwrote Qux

==> xyzzy.txt <==
Foo

(When logged in, completion status appears here.)