Linux Kernel Architecture

Chapter 8: The Virtual Filesystem

dentry cache, which is of great relevance to VFS implementation. At the moment, we can simply regard

adentryas a structure with information on a filename and its inode.

InodeLists

Each inode has ai_listlist head element to store the inode on a list. Depending on the state of the inode,

three main cases are possible:

1. The inode exists in memory but is not linked to any file and is not in active use.


2. The inode structure is in memory and is being used for one or more tasks, usually to rep-
   resent a file. The value of both counters (i_countandi_nlink) must be greater than 0. The
   file contents and the inode metadata are identical to the information on the underlying block
   device; that is, the inode has not been changed since the last synchronization with the stor-
   age medium.


3. The inode is in active use. Its data contents have been changed and therefore differ from the
   contents on the storage medium. Inodes in this state are described asdirty.

Infs/inode.c, the kernel defines two global variables for use as list heads —inode_unusedfor valid but

no longer active inodes (the first category in the above list), andinode_in_usefor all used but unchanged

inodes (the second category). The dirty inodes (third category) are held in a superblock-specific list.

A fourth, less frequent possibility arises when all inodes associated with a superblock are invalidated.

This happens when a media change has been detected for a removable device such that previously used

inodes become meaningless, or when a filesystem was remounted. In all cases, the code ends up in the

functioninvalidate_inodes, and the invalidated inodes are kept on a local list that does not have any

further relevance for the VFS code.

Each inode appears not only in the state-specific list but also in a hash table to support quick access by

reference to the inode number and superblock — this combination is unique throughout the system. The

hash table is an array that can be accessed with the help of the global variableinode_hashtable(also

fromfs/inode.c). The table is initialized during booting in theinode_initfunction fromfs/inode.c.

The messages output indicate the size of the array calculated on the basis of the available RAM.

wolfgang@meitner>dmesg

...

Inode-cache hash table entries: 262144 (order: 9, 2097152 bytes)

...

Thehashfunction fromfs/inode.cis used to compute the hash sum (I won’t describe the implemen-

tation of the hash method). It combines the inode number and the address of the superblock object into

a unique number that is guaranteed to reside within the reserved index range of the hash table.^7 Colli-

sions are resolved as usual by means of an overflow list. The inode elementi_hashis used to manage the

overflow elements.

In addition to the hash table, inodes are also kept on a per-superblock list headed bysuper_block->s_

inodes.i_sb_listis used as the list element.

(^7) There are, however, filesystems in which there is no guarantee that inodes can be identified by reference to their number and asso-
ciated superblock. In this situation, additional elements must be scanned (using filesystem-specific methods);ilookup5is provided
as a front end for this purpose. Currently, the function is not in widespread use except for sysfs and some rarely used filesystems
like OCFS2, but external code for more esoteric filesystems is able to access it.