Structure

Early operating systems implemented Flat file systems, where all files were stored in a single logical location. Flat file systems were simple, but not very practical for organizing large amounts of data. They could quickly become cluttered and difficult to navigate. The introduction of a hierarchical file system, with directories nested within other directories, made it much easier to organize and manage large amounts of data. This innovation paved the way for the modern file systems that we use today, which are much more complex and sophisticated than those of the early computer era.

The Physical filesystem

The exact mechanism by which this data is stored and organized is up to a particular file-system implementation. The operating system’s driver for that file system is responsible for converting the underlying data (such as that stored on a disk, or over a network, or in a disk image file, etc.) into abstract file system objects that form the basis of the physical filesystem from the perspective of the operating system.

In Unix-based operating systems, the physical filesystem object which represents an individual file is called an index node, or inode, for short. It is a structure that contains metadata about the file, such as its type, ownership, access modes (permissions), and timestamps. Additionally, it contains block pointers that contain the location(s) of that file’s data on the corresponding storage device. Importantly, inodes do not contain file name information, which are a part of the symbolic filesystem, and are encoded as dentries, as we will see in a moment. Inodes are assigned unique inode numbers, which conceptually are treated as indices into some abstract array of inode objects–the inode number of a file is therefore its “physical” location within the filesystem.

The two most-basic file types in a Unix-based operating system are regular files, which simply contain data as a sequence of bytes, and directories, which contain lists of other files. The contents of a directory are called directory entries, or dentries, for short. Dentries are simply a tuple containing a file name string, and an inode number. Thus, they associate symbolic names with physical file locations–for this reason, dentries are called “hard links”.

There is no technical restriction on the number of directory entries that may be associated with a particular file’s inode number, so files in a Unix-based operating system can be known by several names. Each inode contains a reference count which tracks how many of these directory entries point it; every time a directory entry is created or destroyed, the reference count is updated. When a reference count reaches 0, the file is considered to be permanently deleted because it is no longer accessible from anywhere within the filesystem.

As an aside, on most file system implementations, a deleted file’s inode and data blocks are simply marked as unused, without immediately overwriting the actual data contained therein, since this would be unnecessarily inefficient. This is the basis of file recovery on Unix operating systems: the inode table is scanned for intact inodes that have reference counts of 0; these inodes represent recently deleted files which can potentially be recovered if their data blocks also have not yet been overwritten.

On most systems, there is a restriction on creating additional hard links that refer to a directory. This is necessary because, if a directory were able to contain references to itself, or one of its ancestors, it would form a self-referential cycle that could become disconnected from the main file system without being fully deleted. The files associated with this cycle would be unreachable, but also continue to persist in the file system.

Common file system operations such as deleting, moving, and renaming files are actually manipulating the underlying hard links that point to the files in question. We have already discussed how a file is deleted by removing all hard links to it. Similarly, a file is moved or renamed by simply creating a new hard link at the new location and then removing the old hard link, without having to move or copy any actual data. This makes file system operations efficient and fast, which is essential to dealing with large numbers of files and directories.

The Symbolic Filesystem

Process primarily interact with a symbolic filesystem that is modeled as a rooted tree using symbolic pathnames to refer to specific files. A symbolic pathname consists of separate components delimited by /, where each path component refers to a particular file within the filesystem. For example, the path /home/bennyb/hello-world.c consists of four components; /, home/, bennyb/, and hello-world.c, each referring to a specific file.

The relationship between the physical and symbolic file systems is mediated by mounting. To resolve a pathname, the operating system walks through each component of the pathname, looking up the inode number corresponding to the next path component by either looking its mount table for a matching pathname, or by scanning the dentry list of the current directory. It repeats this process until reaching the last component of the pathname.

The symbolic file system also supports another type of link called a symbolic link, or symlink for short. A symlink is a special type of file that contains a pathname as its contents. When resolving a component of a pathname that refers to a symlink, that symlink’s path is resolved (recursively, if necessary) to find the file that the symlink points to, and then path resolution continues from there. Unlike a hard-link, symlinks do not affect a file’s reference count, and can refer other directories within the file system. They can also contain pathnames that do not exist in the file system and they can become broken if the files they refer to are moved or deleted.

One important way that symlinks differ from hard links is that they can refer to files in other file systems. Since each file system uses its own inode numbers, there would be no way to specify that a hard link points to inode number N on one filesystem vs the same inode number N in another, so instead hard links are defined as always pointing to files within their own file systems. Additionally, if it were possible to have inter-filesystem hard links, this would present problems if a particular file system were later unmounted, as it would result in broken hard links and erroneous reference counts. Symlinks do not have this problem, and can refer to files in other file systems using their symbolic paths. Of course, if the file system that symlink points to is unmounted or remounted under a different name, then that symlink will be broken, but this avoids any of the technical issues such as broken hard links and incorrect reference counts.