Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

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?

share|improve this question
1  
Are you interested in any particular filesystem(s)? –  Ignacio Vazquez-Abrams Aug 12 '11 at 1:54
2  
In UNIX, everything is a file (historic wisdom). But not every UNIX is Open Source. Gnu 's Not Unix, you know? Open Solaris is an Open Source Unix, while Linux is only a unixoid OS. :) And yes - filesystems - Reiserfs? Ext2-3-4? XFS? NFS? –  user unknown Aug 12 '11 at 4:21
2  
A link is actually a file, too. –  mattdm Aug 12 '11 at 12:06
3  
A symbolic link is a file. A hard link is an edge in the filesystem graph. –  dmckee Aug 12 '11 at 17:28
3  
Advertisement: you may be interested in the Operating Systems Development site proposal. –  Gilles Aug 12 '11 at 23:41
show 3 more comments

4 Answers

up vote 12 down vote accepted

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


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

share|improve this answer
    
Thank you for the elaboration so that I can understand the difference between directories and files at a programmatic level. –  909 Niklas Aug 12 '11 at 2:43
add comment

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

share|improve this answer
1  
+1 for the incredible historical code. –  Bruce Ediger Aug 12 '11 at 12:54
    
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. –  909 Niklas Sep 1 '11 at 15:06
add comment

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.

share|improve this answer
    
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. –  909 Niklas Sep 1 '11 at 15:18
add comment

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

share|improve this answer
    
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.. –  909 Niklas Aug 12 '11 at 2:47
1  
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. –  Bruce Ediger Aug 12 '11 at 12:52
    
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) –  909 Niklas Sep 1 '11 at 15:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.