Page 453 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes
that the file name is padded by an unknown length. That is the meaning of the arrow in Figure
14.32. Then comes the type field: file, directory, etc. The last fixed field is the length of the actual
file name in bytes, 8, 10, and 6 in this example. Finally, comes the file name itself, terminated by
a 0 byte and padded out to a 32-bit boundary. Additional padding may follow that. In Figure
14.32, we see the same directory after the entry for voluminous has been removed. All that is done
is increase the size of the total entry field for colossal, turning the former field for voluminous
into padding for the first entry. This padding can be used for a subsequent entry, of course.

Since directories are searched linearly, it can take a long time to find an entry at the end of a
large directory. Therefore, the system maintains a cache of recently accessed directories. This
cache is searched using the name of the file, and if a hit occurs, the costly linear search is avoided.
A dentry object is entered in the dentry cache for each of the path components, and, through
its i-node, the directory is searched for the subsequent path element entry, until the actual file
i-node is reached.

For instance, to look up a file specified with an absolute path name such as /usr/ast/file the
following steps are required. First, the system locates the root directory, which generally uses
i-node 2, especially when i-node 1 is reserved for bad block handling. It places an entry in the
dentry cache for future lookups of the root directory. Then it looks up the string ‘’usr’’ in the
root directory, to get the i-node number of the /usr directory, which is also entered in the dentry
cache. This i-node is then fetched, and the disk blocks are extracted from it, so the /usr directory
can be read and searched for the string ‘’ast’’. Once this entry is found, the i-node number for
the /usr/ast directory can be taken from it. Armed with the i-node number of the /usr/ast
directory, this i-node can be read and the directory blocks located. Finally, ‘’file’’ is looked up
and its i-node number found. Thus the use of a relative path name is not only more convenient
for the user, but it also saves a substantial amount of work for the system.

If the file is present, the system extracts the i-node number, and uses this as an index into the i-node
table (on disk) to locate the corresponding i-node and bring it into memory. The i-node is put in the
i-node table, a kernel data structure that holds all the i-nodes for currently open files and
directories. The format of the i-node entries, as a bare minimum, must contain all the fields
returned by the stat system call so as to make stat work (see Figure 14.29). In Figure 14.33, we
show the some of the fields included in the i-node structure supported by the Linux file system
layer. The actual i-node structure contains many more fields, since the same structure is also used
to represent directories, devices, and other special files. The i-node structure also contains fields
reserved for future use. History has shown that unused bits do not remain that way for long.

Let us now see how the system reads a file. Remember that a typical call tothe library procedure
for invoking the read system call looks like this: n = read(fd, buffer, nbytes);When the kernel
gets control, all it has to start with are these three parameters,and the information in its internal
tables relating to the user. One of the items in the internal tables is the file descriptor array. It
is indexed by a file descriptor and contains one entry for each open file (up to the maximum
number, usually defaults to 32). The idea is to start with this file descriptor and end up with
the corresponding i-node.

446 LOVELY PROFESSIONAL UNIVERSITY