How are directories implemented in Unix filesystems?

Question

My question is how directories are implemented? I can believe a data structure like a variable e.g. table, array or similar. Since UNIX is Open Source I can look in the source what the program does when it created a new directory. Can you tell me where to look or elaborate on the topic? That a directory "is" a file I could understand and is a directory really a file? I'm not sure that it is true that files are stored "in" files while still in way you could say the word file about nearly anything and I'm not sure what absolutely not is a file since you could call even a variable a file. For example a link is certainly not a file and a link is like a directory but then this violates that a directory is a file?

Answer 1

The directories internal structure is dependent on the filesystem in use. If you want to know precisely what happens, have a look at filesystems implementations.

Basically, in most filesystems, a directory is an associative array between filenames(keys) and inodes numbers(values). Something like this¹:

1167010 .
1158721 ..
1167626 subdir
 132651 barfile
 132650 bazfile

This list is coded in some – more or less – efficient way inside a chain of (usually) 4KB blocks. Notice that the content of regular files is stored similarly. In the case of directories, there is no point in knowing which size is actually used inside those blocks, that's why directories sizes reported by du are multiples of 4KB.

Inodes are there to tie those blocks together, forming a single entity, namely a 'file' in the general sense. They are identified by a number which is some kind of address and each one is usually stored as a single special block.

Management of all this happens in kernel mode. Software just ask for the creation of a directory with a function named int mkdir(const char *pathname, mode_t mode); leading to a system call, and all the rest is performed behind the scenes.

About links structure:

A hard link is not a file, it's just new directory entry (i.e. a name – inode number assoctiation) referring to a preexisting inode entity². This means that the same inode can be accessed from different pathnames. In particular, since metadatas (permissions, ownership, timestamps…) are stored within the inode, those are unique and independant of the pathname chosen to access the file.

A symbolic link is a file and it's distinct from its target. This means that it has its own inode. It used to be handled just like a regular file: the target path was stored in a data block. But now, for efficiency reasons in recent ext filesystems, paths shorter than 60 bytes long are stored within the inode itself (using the fields which would normally be used to store the pointers to data blocks).

—
<sup>1. this was obtained using ls -ai1 testdir.
2. whose type must be different than 'directory' nowadays.</sup>

Answer 2

To expand on the post from Stéphane Gimenez, creating a new directory is the process of creating a new inode with the st_mode value of S_IFDIR (with the permissions mode), creating two entries in the first data block of the new inode with the link(2) system call: '.' which points to this new inode and '..' which points to the parent directory, then creating an entry in the parent directory with the inode and the name of the new directory - the first and last part are done by the system call mknod(2). Also, only root can use mknod(2) these days for such tasks as we're talking about.

For example, mkdir("/home/larry.user/xyzzy", 0666) is essentially the following (this was C code from SysV days[1]):

int mode = 0666;
char newdir[] = "/home/larry.user/xyzzy";
char path1[NAMESZ+4, path2[NAMESZ+4], *p;
mknod(newdir, S_IFDIR|mode);
strcpy(path1, newdir);
strcat(path1, "/."); /* "." link */
link(newdir, path1);
strcat(path1, ".");  /* ".." link */
strcpy(path2, newdir);
if ((p = strrchr(path2, '/') == (char *)0) /* root directory */
    link(".", path1);
else {
    *p = '\0';
    link(path2, path1);
}

1. Haviland&Salama, "UNIX System Programming", 1987, pp69-71.

This was too error prone (and one of the main reasons for fsck) so a mkdir(2) system call was created to be able to do this for you.

Note that amy filesystem object could be created with mknod(2): regular file, directory, device file, symlink, etc. So to answer one of the OP's questions, yes, a directory is a file, which means to say, "it is an object, represented by an inode, residing in a filesystem which behaves with an i/o interface".

Answer 3

if you like to have more information about Unix/Linux filesystems, I recommend you 2 books Understanding the Linux Kernel and The Linux Kernel Development. Those are the best books for understanding Linux kernel.

In the "Common File Model" Unix systems, each directory is regarded a file, which contains a list of files and directories.

In the VFS (Virtual File Systems), the directories are represented in a structure called dentry. The dentry is a C structure with a string name (d_name), a pointer to an inode (d_inode) and a pointer to the parent dentry (d_parent). An inode is a structure for handling information about a file in the filesystem. For instance, if you have the directory /tmp/test/foo, the VFS will create a dentry object for every component in the pathname. SO, it will create a dentry object for /, a second dentry object for the test entry of the root directory and a third dentry object for the foo entry of the test directory.

Answer 4

You could start by reading http://www.freebsd.org/doc/en/books/design-44bsd/book.html#OVERVIEW-FILESYSTEM. For more details get the excellent classic book "The Design and Implementation of the 4.4 BSD Operating System".