2

I am currently reading the book Advance UNIX Programming by W. Richard Stevens and I read there that all the files on UNIX have a number, and that the file names are created just for user convenience. When a directory is entered, the system searches the number for the name entered.

I thought to myself, how do they search for the number? Are the files are stored sorted by name so that they can find them by binary search? Or do they just append new files to the end of the list?

4

There are many different filesystem formats and they make different compromises between performance in different scenarios (large directories vs small directories, read vs write, concurrent access, …), design simplicity (likelihood of bugs, development effort, …), disk overhead (space used for things other than file content), etc.

Older filesystems (e.g. UFS, FFS, ext2, original ext3, …) tend to store directories as an array of entries (each entry contains a file name, an inode number and possibly some additional metadata) and to do a linear search. New files are added at the first free entry in the array; if there is no free entry, the array is first enlarged. This results in bad performance with large directories.

Newer filesystems (e.g. ext3 with the dir_index option, ext4, zfs, btrfs, reiserfs, HFS, HFS+, …) tend to store directories as a data structure with logarithmic-time lookup, some kind of balanced search tree, hash table, or a combination of the two (balanced search tree of hashes) — typically some variant of a B-tree. This makes the filesystem code more complex but keeps performance good with large directories.

2

The number is called an inode. Ext4, one of the more popular Linux filesystem types, makes use of a hash tree, see kernel.org - Ext4 Disk Layout.

More details of hash trees at wikipedia.

2

This is dependent on the file system. A long time ago the Unix directory was in essence a file consisting of 16 byte records, two bytes for the inside number and 14 bytes for the file name. This is the reason for the old-time 14 character limit on file names. The records were not sorted, so a linear search through the file was required.

More modern file systems like Linux's Ext4 has a hash table to speed up the search.

0

Pedant alert: the description is not complete. File names cannot be described as only a convenience for users. File names have turned out to be extremely important in unix-based systems.

Inode numbers cannot have meaning because they are chosen by the filesystem module. Originally they identified a slot into the inode table stored on-disk. The other parts of the system need to access files which have a specific meaning, e.g. /dev/tty1 or /etc/passwd.

Without holding you to a specific word, "convenience" is too trivial to describe the mechanism, which is used to provide the user interface to select commands such as cat or ed by name.

If there were not directories of file names, you would very soon have to invent some very similar registries of names for the inode numbers to support these uses.

The directory entries . and .. also have a special meaning. Virtual filesystems such as proc provide their own meaning using filenames, e.g. making /proc/1/comm available to provide information on process 1. The VFS also allows the use of different filesystems, which do not have to be based on unix and might not work with the same exact concept of inode numbers.

ZFS seems to think both file names and inode metadata, like permissions, belong in a separate layer. I have yet to understand what advantage this provides. It seems to be more a way to provide different performance knobs for file-equivalent-objects when used to store nested filesystems.

Also users generally can't open files by inode number. If they could, you wouldn't be able to control access to a file through the permissions of the containing director{y,ies}...

Perhaps another way to look at the last point is that it's a feature of directories. The whole principle of a directory is to map filenames, so without that they don't really have any effect.

Wait, you say, they would still have an effect as a container for references to files aka "hard links". You can have files listed in multiple directories; removing a file from one directory (unlink) does not actually delete it, if it still remains in another directory. Hard links are an interesting part of the unix implementation, but AFAIK they never really found any utility! They're generally regarded only as an opportunity for confusion. An example of exposing an implementation detail because it made it very easy to provide interesting features, without really considering whether the feature was necessary. Similar to the "billion dollar mistake", though this particular design flaw has not been so dangerous.

That said, it's worth noting the way directories guarantee the existence of the files they contain. If you wanted to implement some other system to identify files, you would have to consider the possibility that deleting a file would leave you with an entry referring to a non-existent file, or even a new and unrelated file which was assigned the same inode number later on.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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