Get an Email

..when I post something to the blog! It'll be interesting and worth the read - really!

Directories, Symlinks, iNodes…oh, my!

This is an article posted on macintouch.com about directories, symlinks, inodes, etc – it’s a handy explanation of some of the basics of filesystems that I found useful enough to stash here for future reference. Many thanks to David Charlap for taking the time to post on Macintouch!


 

From Macintouch.com by David Charlap

There’s a lot of talk here (in the context of Time Machine) about “hard links”, “symbolic links”, “aliases” and similar concepts, so I thought a discussion about file systems and the terminology might be useful for our readers, especially those without a computer science background.

Under the covers, any modern file system tracks three things. Directories, files, and the disk-blocks that store the file data.

At the lowest level, there are disk blocks. Each block holds a fixed amount of data and typically belongs to exactly one file. (Ignoring some obscure features like Berkeley UFS’s “fragments” which can allow one block to hold data belonging to up to 8 files.) Although the details differ for different kinds of file systems, they all manage a collection of fixed-size blocks and have a mechanism for recording which blocks are in-use, which are free and which are “bad” (meaning they should never be used, usually because they failed some automated test.)

Blocks are organized into files. A file consists of a collection of blocks (organized as one or more sequence of blocks) to hold the file’s data, and meta-data to store information about the file (like timestamps, permissions, file size, file type, etc.) The details of how this data is organized varies for each kind of file system.

The key fact to take away from the above is that every file is ultimately represented by a single well-defined structure. In the Unix world, this is known as the “inode“. Other operating systems may have other names for it, but in all cases there is a single structure that represents a file, describes the blocks that comprise the file and stores (or describes the blocks containing) that file’s meta-data. For the rest of this message, I will use the term “inode” to represent this structure, because it is less confusing than words like “file” which have different meanings in different contexts.

(FYI, although I said every file system uses an inode or some similar construct, this isn’t 100% correct. Some old file systems, like those designed for floppy disks, don’t use such a structure. For instance the FAT file system stores metadata in the directory entries (see below) and uses a “FAT table” shared by all files on the volume to identify a file’s disk blocks. Apple DOS 3.3 stored metadata with directory entries and had each data-block contain a pointer to the next block in that file (as a linked-list). But modern file systems all use something functionally like an inode.)

One important thing to note here is that the inode is not directly accessible by application software, or even more parts of the OS itself. It is purely internal to the file system and is only used by the file system driver software.

In order to provide access to these files, all file systems implement directories (aka “folders”). A directory is typically implemented as a file (again, old file systems may treat directories as something special, but modern file systems implement them as a specialized kind of file) that contains file-names and data to associate each name with the inode that describes the corresponding file. Different file systems will, of course, use different data structures in these directory files, and some may store small amounts of meta-data with the file-name, but ultimately, all directories consist of a collection of file-names and data describing the inode that describes the file itself.

At this point, you may be asking yourself “if a directory is a file, and you need a directory to access a file, how can you get started and ultimately access anything?”. The answer is that each volume has a “root directory” which is a directory file stored in a well-known location, so the file system software can access it without any other directory.

In standard Unix terminology, a single record in a directory (file-name and inode number) is known as a “hard link” or sometimes just a “link”. It is also sometimes known as “directory entry” and you’ll find me using that term quite a bit.

In some file systems (like HFS, I believe), you can only have a single link to a particular file. If you have two directory entries linking to the same file, it is an error (known as a cross-linked file) and is something that disk repair utilities will complain about and try to fix.

In other file systems (like HFS+, all Unix file systems, and others), there is nothing wrong with multiple directory entries linking to the same inode. It’s not a problem. Remember that no matter how many directory entries link to that inode, it’s still only one inode, and therefore only one file.

An obvious question here is “how does the operating system know when to delete a file if there are multiple links to it?” When the file system only allows one directory entry to link to a single inode, then the logic is simple – you free the inode and its blocks when that directory entry is deleted. A file system that supports multiple directory entries to link to an inode must be able to track this. Typically, the inode contains a count of how many directory entries link to it, so it won’t be freed until that count reaches 0 (when the last link was removed.) (On Unix and Unix-like systems, it’s a little more complicated because you can delete links while applications have the file open, so the OS won’t actually free the inode and disk blocks until the count of links goes to 0 and the count of open handles to that file also goes to 0.)

When we say we are creating a “hard link” to a file, it means we are creating a new directory entry that links to the inode of a file that already exists.

You might ask “if I create additional hard links, what happens when the original directory entry is deleted?” For operating systems that follow Unix semantics (including Mac OS X), the answer is “nothing”. All hard links to a file are equivalent. There is no concept of the “original” directory entry. If you create a file, create a second link to it, then delete the original link, the file remains as it was, with the second link being the sole remaining way to access it.

And this is the magic behind Time Machine. If you have a backup set, and you create a second backup set where nothing has changed, no new files (that is, no new inodes and no data blocks) are allocated for that backup. It simply creates new hard links (that is, directory entries) that point to the inodes used by the previous backup.

Well, that’s not 100% accurate. Historically, Unix systems would not allow you to create additional hard-links to directories – only to other kinds of files. This is not for any technical reason, but for a practical reason. If you’re sloppy (or malicious) you could use hard-links to create an infinite loop of directories. Software that walks through your file system could end up in an infinite loop and never even realize it. So, by convention (and enforced by the system APIs), you are prohibited from creating hard links to directories.

Time Machine changed this convention. Apple added the ability to create hard-links to directories in order to minimize the amount of data used by each backup. This is because a typical Mac OS X system has hundreds of thousands of files, so a backup that duplicates all the directory entries (even if they are all links to pre-existing files) will still consume a lot of storage and take a lot of time to create. By allowing hard-links to directories, they can avoid this problem. If an entire sub-tree of directories (and the files contained within) have not changed, then Time Machine can just create a hard-link to the pre-existing directory.

So, now that we know what a hard link is, what is a “symbolic link?”

Unlike a hard link (which is just a directory entry,) a symbolic link (aka “symlink”) is a complete file, containing a directory entry, an inode and data blocks. Its directory entry does not link to the original file’s inode. Instead, the symlink’s data contains the path name of the other file.

When you use the OS’s API to open a file that is a symlink, the OS will recognize it as such (via the metadata). It will read the path-name, and then try to open that file. If that file is also a symlink, then it will read that symlink’s path-name and open its file, and so on, until it ultimately opens the actual file or finds that it can’t (e.g. because there is no actual file at that location.)

(There are special APIs for opening the symlink itself, for when that is needed, but the normal file APIs open whatever the symlink’s path-name is referencing.)

So now that we know this, what are some of the practical differences between hard-links and symbolic links?

* All hard-links to a given file must exist on the same volume. You can’t have a directory entry on one volume linking to an inode on a different volume. Symbolic links, on the other hand, can point to any file anywhere, because it only references a path-name.

* A symbolic link does not prevent the referenced file’s inode from being deleted. If you create a file, create a symlink to that file, then delete the original file’s link, the file is deleted. The symlink will remain behind, but trying to open it will fail because its path-name is referencing a file that doesn’t exist. If you tried this with hard-links, the file/inode would not be deleted (because one link remains) and would continue to be accessible via the remaining directory entry.

* You can create a symlink that doesn’t point to any file. The ln command, for instance, will let you provide any syntactically valid path-name as the target of the link. Of course, if there is no directory entry at that location, trying to open a file via the symlink will fail.

* If a symlink’s path is not pointing at any file, and a directory entry is subsequently created at that location, the symlink will be able to open the file at that location!

Note that this has the potential for introducing security holes, depending on where the symlink is created and what its path is referring to. This is why (for example), the Apache web server (in its default configuration) will not open a symlink unless it and the linked-to file are owned by the same user.

* It also means that the following sequence will produce completely different results with hard vs symbolic links:
1: Create file 1 at location A
2: Create a link to file 1 at location B
3: Delete the link at location A
4: Create file 2 at location A

If you used a symbolic link in step 2, then file 1 will end up deleted and the link at location B will open file 2 (via its name at location A)

If you used a hard link in step 2, then no inodes/files will be deleted. The link at location B will open file 1, and the link at location A will open file 2.

So what about aliases? How are they different from symbolic links?

An alias is a Mac-specific concept. It was introduced in System 7, and actually predates the HFS+ file system. It has evolved quite a lot since then, but the basic concept remains.

Like a symbolic link, an alias is a file. Unlike a symbolic link, it contains much more than just the path to a file. An alias contains a full set of Finder-compatible metadata (originally stored in the alias’s resource fork, but may also be stored in its data fork today) that describes the location of a file. Like a symbolic link, it contains a path-name. It also contains many other Mac-specific data structures that identify the referenced file. It may also contain icon data and have its own set of Finder info. The content of alias files has grown over the years as Apple has added new capabilities, but ultimately, aliases contain the identity of another file, in a variety of different representations.

How do aliases differ from symbolic links? In the Finder, they are displayed identically, which is a shame and can lead to confusion, because they behave differently:

* Mac OS X’s Unix APIs do not recognize aliases. If you use one of them to open an alias, you will open the alias file itself, not the file it refers to.

* If you use Mac APIs (Carbon and Cocoa) to open an alias, the referenced file will be opened.

* If the referenced file is moved from its original location, an alias to it may not always break. Depending on where it is moved to and which APIs are used to perform the move, some of its data (not the path, of course) will remain valid. Opening the alias will open the original file if any of the alias data remains valid. Over the years (and subsequent versions of Mac OS), the number of actions that will break an alias have gone down, although there are definitely thing you can do to the referenced file that will break the alias.

* When double-clicking an alias in the Finder, if some of its data is invalid (e.g. because the file moved or was renamed or replaced), but the referenced file can still be located (because not all of the alias data is invalid), I believe the Finder will auto-update the alias’s data to accurately reflect the new information about that file.

Comments are closed.