While dealing with the Virtual Filesystem of Linux I have come across a little problem of understanding how pathnames are resolved if they are already cached as dentries in the dentry cache.
I know that the different dentries are organized in a hash table to speed up future lookups of already resolved pathnames. The book I am reading at the moment is saying the following:
Creates a hash value; this function is a filesystem-specific hash function for the dentry hash table. The dentry parameter identifies the directory containing the component. The name parameter points to a structure containing both the pathname component to be looked up and the value produced by the hash function.
The hash table is implemented by means of a dentry_hashtable array. Each element is a pointer to a list of dentries that hash to the same hash table value. The array's size usually depends on the amount of RAM installed in the system; the default value is 256 entries per megabyte of RAM. The d_hash field of the dentry object contains pointers to the adjacent elements in the list associated with a single hash value. The hash function produces its value from both the dentry object of the directory and the filename.
Understanding the Linux Kernel
Let's assume that we have the following path "/home/test/file". Now the VFS creates dentries for "/", "home", "test" and "file".
Now I don't understand how the corresponding hash value for each dentry is calculated and how the VFS looks up a pathname through these cached dentries in the hash table. In my understanding the VFS does the following:
- Calculate hash value of dentry for "/" and filename "home"
- Look up hash value for corresponding dentry of "home" in hash table
- Calculate hash value of dentry for "home" and filename "test"
- Look up hash value for corresponding dentry of "test" in hash table
- Calculate hash value of dentry for "test" and filename "file"
- Look up hash value for corresponding dentry of "file" in hash table
But on some websites on the Internet it sounds like the VFS only hashes the complete pathname at once and looks up the corresponding dentry with the resulting hash value.
So it would be great if someone could bring some light into the darkness.