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?

Solution 1

The internal structure of directories is dependent on the filesystem in use. If you want to know precisely what happens, have a look at filesystem 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 these blocks. That's why the sizes of directories reported by du are multiples of 4KB.

Inodes are there to tie 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 asks 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 a new directory entry (i.e. a name – inode number association) 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, these are unique and independent 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>

Solution 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".

Solution 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.

Solution 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".

View more solutions

Comments

[Ignacio Vazquez-Abrams]

Are you interested in any particular filesystem(s)?

[Niklas Rosencrantz]

Any UNIX. I looked at HammerFS and I use default ubuntu 11.04 and ask about similarities and/or differences.

[Ignacio Vazquez-Abrams]

"UNIX" is not a filesystem. Did you mean UFS?

[mattdm]

A link is actually a file, too.

[dmckee --- ex-moderator kitten]

A symbolic link is a file. A hard link is an edge in the filesystem graph.

[Gilles 'SO- stop being evil']

Advertisement: you may be interested in the Operating Systems Development site proposal.

[Niklas Rosencrantz]

Thank you for the elaboration so that I can understand the difference between directories and files at a programmatic level.

[Niklas Rosencrantz]

Thanks for the link. I understand both files are directories basically are arrays that get interpreted either as files or directories. Please correct me if I'm wrong..

[Admin]

Directories are traditionally just specially formatted files, but that's no longer true: en.wikipedia.org/wiki/ReiserFS#Design In ReiserFS and some others, directories are entries in a database. Directories may act as arrays, but that's just the programming abstraction.

[Niklas Rosencrantz]

Thank you for the very interesting answer. I understand and think I can also look in the source for the program touch which creates an empty file and see what it does.

[Niklas Rosencrantz]

Thank you very much for pointing out the details. Now I think I understand more how filesystems work still wondering how and why the program locate does its works and how this related to updating the locate program by running updatedb (spec I use PC-BSD, DragonflyBSD and Ubuntu Natty booting from Live CDs and benchmarking different installs and interfaces)

[Niklas Rosencrantz]

Thank you Dimitri. I want to understand why some project chose a particular data structure like a B-Tree, a binary tree, a trie or associative array. I think it's important to chose a suitable data strcture / data model. Learning about the different implementations gives the details I'm looking for.