In the first part, we saw what a directory is and gave some fuzzy ideas on how it is implemented. Let's now outline the most common operations run on directories: lookup and readdir.

The lookup operation receives a path component name (a string without slashes) and returns the node pointed to by this name within the directory, assuming, of course, that the entry exists. Otherwise, it tells the caller that the entry is missing or incorrect (i.e., not a directory). This operation takes advantage of the name cache because it must be fast; keep in mind that lookups are executed extremely often.

The implementation of the lookup operation, however, is very complex. It is cluttered by a weird locking protocol and has a lot of special cases. These include access advices, a technique used to tell the operation what kind of lookup is happening: a creation, a removal, a rename or a simple lookup. UFS uses these to locate empty holes in the directory while looking for an entry, among other things. tmpfs uses it to avoid two lookups for the same file on some operations, such as the creation.

On the other hand, we have the readdir operation, the one used to read the contents of a directory. This operation is conceptually simple, as all it has to do is read as much entries as possible from the offset given to it. These entries are returned in a standard format, described in getdents(2).

However, there is a tricky thing in readdir: the cookies. They are used by the NFS server to map directory entries to offsets within it so that further lookups can be done in a more efficient manner. For each entry returned by readdir, a cookie is also returned that specifies its physical offset inside the directory. A further call to this operation using the cookie's value could restart the read at the point where the entry lives.

It is also interesting to note that some file systems return fake cookies because they do not have physical offsets within them — in other words, they are not stored on disk. This happens in, e.g., tmpfs or kernfs.

Post suggested by Pavel Cahyna.

Go to posts index

Comments from the original Blogger-hosted post: