The Directory Cache
To speed up accesses to commonly used directories, the VFS maintains a cache of
As directories are looked up by the real file systems their details are added into
the directory cache.
The next time the same directory is looked up, for example to list it or open a
file within it, then it will be found in the directory cache.
Only short directory entries (up to 15 characters long) are cached but this is
reasonable as the shorter directory names are the most commonly used ones.
For example, /usr/X11R6/bin is very commonly accessed when the X server is
The directory cache consists of a hash table, each entry of which points at
a list of directory cache entries that have the same hash value.
The hash function uses the device number of the device holding the file system and
the directory's name to calculate the offset, or index, into the hash table.
It allows cached directory entries to be quickly found.
It is no use having a cache when lookups within the cache take too long to find entries,
or even not to find them.
In an effort to keep the caches valid and up to date the VFS keeps lists of
Least Recently Used (LRU) directory cache entries.
When a directory entry is first put into the cache, which is when it is first
looked up, it is added onto the end of the first level LRU list.
In a full cache this will displace an existing entry from the front of the
As the directory entry is accessed again it is promoted to the back of the
second LRU cache list.
Again, this may displace a cached level two directory entry at the front of
the level two LRU cache list.
This displacing of entries at the front of the level one and level two LRU lists
The only reason that entries are at the front of the lists is that they have not
been recently accessed.
If they had, they would be nearer the back of the lists.
The entries in the second level LRU cache list are safer than entries in the level one
LRU cache list.
This is the intention as these entries have not only been looked up but also
they have been repeatedly referenced.