Directory Organization

In vsfs (as in many file systems), directories have a simple organization; a directory basically just contains a list of (entry name, inode number) pairs. For each file or directory in a given directory, there is a string and a number in the data block(s) of the directory. For each string, there may also be a length (assuming variable-sized names).

For example, assume a directory dir (inode number 5) has three files in it (foo, bar, and foobar_is_a_pretty_longname), with inode numbers 12, 13, and 24 respectively. The on-disk data for dir might look like:

inum	reclen	strlen	name
5	12	2	.
2	12	3	..
12	12	4	foo
13	12	4	bar
24	36	28	foobar_is_a_pretty_longname

In this example, each entry has an inode number, record length (the total bytes for the name plus any leftover space), string length (the actual length of the name), and finally the name of the entry. Note that each directory has two extra entries, . “dot” and .. “dot-dot”; the dot directory is just the current directory (in this example, dir), whereas dot-dot is the parent directory (in this case, the root).

Deleting a file (e.g., calling unlink()) can leave an empty space in the middle of the directory, and hence there should be some way to mark that as well (e.g., with a reserved inode number such as zero). Such a delete is one reason the record length is used: a new entry may reuse an old, bigger entry and thus have extra space within.

You might be wondering where exactly directories are stored. Often, file systems treat directories as a special type of file. Thus, a directory has an inode, somewhere in the inode table (with the type field of the inode marked as “directory” instead of “regular file”). The directory has data blocks pointed to by the inode (and perhaps, indirect blocks); these data blocks live in the data block region of our simple file system. Our on-disk structure thus remains unchanged.

Again, we should note that this simple linear list of directory entries is not the only way to store such information. As before, any data structure is possible. For example, XFS“Scalability in the XFS File System” by Adan Sweeney, Doug Doucette, Wei Hu, Curtis Anderson, Mike Nishimoto, Geoff Peck. USENIX ’96, January 1996, San Diego, California. The first attempt to make scalability of operations, including things like having millions of files in a directory, a central focus. A great example of pushing an idea to the extreme. The key idea behind this file system: everything is a tree. We should have a chapter on this file system too. stores directories in B-tree form, making file create operations (which have to ensure that a file name has not been used before creating it) faster than systems with simple lists that must be scanned in their entirety.

ASIDE: LINKED-BASED APPROACHES

Another simpler approach in designing inodes is to use a linked list. Thus, instead of having multiple pointers inside an inode, you just need one to point to the first block of the file. To handle larger files, add another pointer at the end of that data block, and so on, and thus you can support large files.

As you might have guessed, linked file allocation performs poorly for some workloads; think about reading the last block of a file, for example, or just doing random access. Thus, to make linked allocation work better, some systems will keep an in-memory table of link information, instead of storing the next pointers with the data blocks themselves. The table is indexed by the address of a data block $D$; the content of an entry is simply $D$’s next pointer, i.e., the address of the next block in a file which follows $D$. A null-value could be there too (indicating an end-of-file), or some other marker to indicate that a particular block is free. Having such a table of next pointers makes it so that a linked allocation scheme can effectively do random file accesses, simply by first scanning through the (in memory) table to find the desired block, and then accessing (on disk) it directly.

Does such a table sound familiar? What we have described is the basic structure of what is known as the file allocation table or FAT file system. Yes, this classic old Windows file system, before NTFS“Inside the Windows NT File System” by Helen Custer. Microsoft Press, 1994. A short book about NTFS; there are probably ones with more technical details elsewhere., is based on a simple linked-based allocation scheme. There are other differences from a standard UNIX file system too. For example, there are no inodes per se, but rather directory entries that store metadata about a file and refer directly to the first block of said file creating hard links impossible. See Brouwer“The FAT File System” by Andries Brouwer. September, 2002. Available online at: http://www.win.tue.nl/ ̃aeb/linux/fs/fat/fat.html. A nice clean description of FAT. The file system kind, not the bacon kind. Though you have to admit, bacon fat probably tastes better. for more of the inelegant details.