Introduction

Hello, and welcome back to CS631 "Advanced Programming in the UNIX Environment". With this video segment we are starting the material for week four, diving deeper into file systems and directories as covered in the W. Richard Stevens APUE book, chapters 4 and 6. As we've seen in our previous discussions, certain file system properties and concepts are encountered on a regular basis, and to better understand them, it would be useful to visualize the file system and some of the corresponding data structures.

Disk partitions

Let's take a look: In the beginning, there was a disk... well any storage medium, really, but let's consider a hard disk. A hard disk can be divided into smaller partitions. While there are different types of partitions - BIOS partitions, say, or operating system specific partitions - for our purposes the distinction doesn't matter much. On our reference VM running NetBSD, we can inspect the OS specific partition table via the disklabel(8) command. Here we see a description of the physical disk. Well, it's a virtual disk, but the OS doesn't know that and thinks there's an actual physical device there, so it tries best to describe what that looks like. One of the factors of the physical disk that we have seen before is the physical block size shown here to be a very not surprising 512 bytes. Further down, we see how the disk is divided into partitions: there's one partition describing the entire disk starting at offset 0 and ending at the very last sector; then there's a partition describing the portion of the disk set for use by the NetBSD operating system, starting at offset 64, leaving the first sector available to the BIOS partition table; the root partition, where we create our entire file system on, is partition 'a'; and we also carved out a small, second partition for use as swap. So once we've created our partition table, we can then create a file system on each partition. Or not, as in the case of our swap partition, where we use the raw disk as a place to stash memory when needed. The file system organizes the various cylinder groups and provides some addressing of the structures in each in a so-called "superblock". Now each cylinder group in turn contains the actual data blocks, the parts where we store the actual bytes that make up our files, as well as a list of inodes and blocks set aside for the metadata associated with the inodes, the inode blocks. Since the entire structure of the file system is written in the super block, it'll be pretty disastrous if you lost this one block. So the file system replicates the super block in cylinder groups, thereby allowing recovery of the file system from a corrupted superblock. Finally, the actual data that we discussed when we talk about files and directories are stored in different groups of data blocks, the inode data blocks and the file data blocks. Here we see how the metadata about a file -- all the information that we are now so familiar with from our discussion of the struct stat -- is stored separately from the actual bytes of the file.

Illustration of links

Here's another view of this: consider a regular file identified by inode number 123, pointing to a number of data blocks somewhere on the disk. Let's recall from our previous lecture that the data stored in the inode does not include the file name. File names are stored as directory entries only, remember? Such a directory entry mapping a file name to an inode is known as a hard link, and we can visualize it as shown here. Note that a hard link is not a different name for an existing file; the name of the file is itself the hard link. And so it's entirely possible to have multiple such links to a given inode. Such links may exist in the same directory, where they would then have to have a different file name, or in another directory elsewhere on this disk, as shown here. In this case, the name of the link in that second directory could be the same as the name of the link in the first directory; the path name to each would be different, however. Okay, so let's take a look at directories: Here we see two directories: one at inode 1267, and one at inode 2549. The unix file system may store the contents of a directory and reserve directory data blocks for efficiency reasons possibly kept separate from the data blocks used for regular files, but for our purposes that is an implementation detail we need not care about. Now if you create an empty directory and you look at the output of 'ls -a', you will note that it contains two entries already: '.' and '..'. '.' refers to the current directory; that is inside of every directory, there's a mapping referencing the directory itself: dot. At the same time, there's another entry called '..', which refers to the parent directory. These two entries are present for every directory and allow you to maneuver the file system hierarchy via relative paths. Now any directory must also have another name - what we would usually call its "real" name. That name is the mapping found in the directory's parent directory, since every directory has to exist somewhere. This illustration here may help make this a little less confusing. On the right hand side, we see a directory at inode number 1267. We don't know what this directory is called. The entry '.' in this directory points to inode number 1267, the directory data blocks of which point to the disk where we find the entries. The entry '..' here has an inode number not shown in this image, which would be this directory's parent directory. Now in this directory at inode number 1267 has a third entry in addition to '.' and '..': a file of type directory named 'testdir', pointing at inode number 2549. The directory blocks for this directory are shown over here. This directory known as 'testdir' in the directory with inode number 1267 has two entries: '.' - inode number 2459 - and '..' - inode number 1267, which points to the parent directory at inode number 1267, which contains the 'testdir' link.

Inodes

Seeing how these hard links are mappings between inode and directory entries, and looking back at our illustration of the file system on the given partition, we understand that such hard links can only exist within the same file system. If this doesn't seem obvious, consider that you might have more than one partition in use. In that case, you'd have a second file system on the second partition. The second file system would also have an inode map, and logically you might have, for example, an inode with number 1234 on the first file system, just like you have an inode with number 1234 in the second file system. So as noted in our previous discussions, this is why the st_dev field is required to, in combination with the st_ino field uniquely identify a file. Okay, we already know that the inode contains all the information from the struct stat, and with the illustration at hand, we can also understand what the meaning of the st_nlink count field is: the number of hard links that exist for this particular file. This count can be used to determine when the data blocks associated with a file can be freed: only if the number of things pointing to this inode is 0 - and no other process has an open file handle for this inode - can you mark the blocks as available. Note also that based on this illustration you can see that the st_nlink count for any directory must be at least two, since every directory has two names: '.' and whatever the name is that exists in its parent directory. The next thing that this illustration help us understand is that moving a file within the same file system is a really fast operation, since no data blocks need to be accessed. In fact, moving a file within the same file system really doesn't move anything! Instead, you simply create a new link, temporarily yielding two simultaneous names for the same file, and then removing the old directory entry and that's it. Note how at no time did we go out to the disk blocks and copied those around. Of course this only works when moving a file within the same file system; if you were to move a file from one file system or partition to another, you'd have to actually first copy the file to the other partition, then remove the old entry. You can verify this for yourself by creating a large file and renaming it on a single file system, and then observing how long it takes to move it to another file system.

Recap

All right, let's take a break here. Having the Unix file system visualized as we did should help us understand the concept of hard links and directories, and some of the operations involved. We'll show more practical examples in our next video segment, but perhaps start playing around in your terminal with a 'mkdir', 'touch', and of course, 'ls' commands to inspect the inode numbers and link counts of various files and directories you create. Think about edge cases, too! For example, if every directory must have a parent directory, what's the parent directory of the root of the file system, "/"? What are the inodes of '.' and '..' there? Well, more on that next time when we also look at the system calls used to create, remove, and rename directories and links, including symbolic links. Until then, thanks for watching!

Outro

Cheers.