The VFS Inode Cache
As the mounted file systems are navigated, their VFS inodes are being continually
read and, in some cases, written.
The Virtual File System maintains an inode cache to speed up accesses to all of
the mounted file systems.
Every time a VFS inode is read from the inode cache the system saves an access to
a physical device.
The VFS inode cache is implmented as a hash table whose entries are pointers to
lists of VFS inodes that have the same hash value.
The hash value of an inode is calculated from its inode number and from the device
identifier for the underlying physical device containing the file system.
Whenever the Virtual File System needs to access an inode, it first looks in the
VFS inode cache.
To find an inode in the cache, the system first calculates its hash value and then uses
it as an index into the inode hash table.
This gives it a pointer to a list of inodes with the same hash value.
It then reads each inode in turn until it finds one with both the same inode
number and the same device identifier as the one that it is searching for.
If it can find the inode in the cache, its count is incremented to show that it
has another user and the file system access continues.
Otherwise a free VFS inode must be found so that the file system can read the
inode from memory.
VFS has a number of choices about how to get a free inode.
If the system may allocate more VFS inodes then this is what it does; it
allocates kernel pages and breaks them up into new, free, inodes and puts them
into the inode list.
All of the system's VFS inodes are in a list pointed at by first_inode as well
as in the inode hash table.
If the system already has all of the inodes that it is allowed to have, it must
find an inode that is a good candidate to be reused.
Good candidates are inodes with a usage count of zero; this indicates that the
system is not currently using them.
Really important VFS inodes, for example the root inodes of file systems always have
a usage count greater than zero and so are never candidates for reuse.
Once a candidate for reuse has been located it is cleaned up.
The VFS inode might be dirty and in this case it needs to be written back to the file system
or it might be locked and in this case the system must wait for it to be unlocked before
The candidate VFS inode must be cleaned up before it can be reused.
However the new VFS inode is found, a file system specific routine must be called
to fill it out from information read from the underlying real file system.
Whilst it is being filled out, the new VFS inode has a usage count of one and is
locked so that nothing else accesses it until it contains valid information.
To get the VFS inode that is actually needed, the file system may need to access
several other inodes.
This happens when you read a directory; only the inode for the final directory is
needed but the inodes for the intermediate directories must also be read.
As the VFS inode cache is used and filled up, the less used inodes will be discarded
and the more used inodes will remain in the cache.