The Kernel View of File Systems

This file system's native block size

  20 0    4 0 int        vfs_bsize

For exported file systems (NFS) this is the UID remote "root" 

users are remapped to and the export state flag

  24 0    2 0 u_short    vfs_exroot

  26 0    2 0 short      vfs_exflags

This points to the file system's type-specific in-core data 

structures

  28 0    4 0 *          vfs_data

A reference count of processes currently sleeping on the file

system's mount point

  32 0    4 0 int        vfs_icount

The file system's specific type (HFS, VxFS, NFS, CDFS, ...)and 

its unique id

  36 0    2 0 short      vfs_mtype

  40 0    4 0 int        vfs_fsid[0]

  44 0    4 0 int        vfs_fsid[1]

A log pointer, the most recent mount timestamp, file system

name, device number (Major+minor device number), and a chain

pointer to DNLC entries referencing this file system

  48 0    4 0 *          vfs_logp

  52 0    4 0 int        vfs_mnttime

  56 0 1024 0 char[1024] vfs_name

1080 0    4 0 int        vfs_dev

1084 0    4 0 *          vfs_ncachehd

Listing 8.4. q4> fields struct vfsops

The following pointers form a vector jump table to type-

specific operational routines in the kernel

 0 0 4 0 * vfs_mount

 4 0 4 0 * vfs_unmount

 8 0 4 0 * vfs_root

12 0 4 0 * vfs_statvfs

16 0 4 0 * vfs_sync

20 0 4 0 * vfs_vget

24 0 4 0 * vfs_getmount

28 0 4 0 * vfs_freeze

32 0 4 0 * vfs_thaw

36 0 4 0 * vfs_quota

40 0 4 0 * vfs_mountroot

44 0 4 0 * vfs_size

The Type-Specific In-Core Data Structures

Each file system type requires its own specific in-core data. Figure 8-13 illustrates the point.

In general, the in-core data has a copy of the file system's superblock, a pointer to the kernel's copy of the inode / vnode to which the file system is mounted, and copies of the file system's allocation tables.

In the case of HFS, the kernel-resident structures include a mount structure (with pointers to the mount point's inode / vnode ), a pointer back to the file system's vfs structure, and a pointer to a copy of the superblock maintained in the buffer cache (more on the buffer cache later in this chapter). Let's examine the HFS mount and fs (superblock) structures in Listings 8.5 and 8.6.

Listing 8.5. q4> fields struct mount

First are forward and backward linkage pointers to a hash list

   0 0 4 0 *       m_hforw

   4 0 4 0 *       m_hback

Next is a pointer to the file system's vfs structure, the 

block device number (major and \minor number) on which the 

file system resides, and a pointer to the buffer header which

maps the in-core copy of the file system's superblock

   8 0 4 0 *       m_vfsp

  12 0 4 0 int     m_dev

  16 0 4 0 *       m_bufp

  20 0 4 0 int     m_maxbufs

The raw device number is also recorded here

  24 0 4 0 int     m_rdev

  28 0 4 0 *       m_nodes.m_inodp

  28 0 4 0 *       m_nodes.m_cdnodp

  32 0 4 0 *       m_qinod

Mount flags are stored here

  36 0 4 0 int     m_flag

  40 0 2 0 u_short m_qflags

  44 0 4 0 u_int   m_btimelimit

  48 0 4 0 u_int   m_ftimelimit

A pointer to the file system's root inode/vnode in-core, a 

reference count, and a pointer to the mount point's in-core

inode/vnode

  52 0 4 0 *       m_rootvp

  56 0 4 0 u_int   m_ref

  60 0 4 0 *       m_iused

Listing 8.6. q4> fields struct fs

0 0   4 0 int       fs_unused[0]

   4 0   4 0 int       fs_unused[1]

First we have the file system's super block address, the

offset of the cylinder group data block, the inode blocks, and 

the first data block following the cylinder groups

   8 0   4 0 int       fs_sblkno

  12 0   4 0 int       fs_cblkno

  16 0   4 0 int       fs_iblkno

  20 0   4 0 int       fs_dblkno

  24 0   4 0 int       fs_cgoffset

  28 0   4 0 int       fs_cgmask

Next is the last modification timestamp, the number of blocks

(total space), and number of data blocks (minus the metadata

overhead) in the file system.

  32 0   4 0 int       fs_time

  36 0   4 0 int       fs_size

  40 0   4 0 int       fs_dsize

Additional static and tunable parameters include the number of

cylinders per group, block and fragment sizes, number of 

fragments in a block (1,2,4,8), minimum reserved free space

(applies only to non-superuser allocation requests),

rotational delay for writing sequential blocks (also known as

interleave), and drive speed (in revolutions per second)

  44 0   4 0 int       fs_ncg

  48 0   4 0 int       fs_bsize

  52 0   4 0 int       fs_fsize

  56 0   4 0 int       fs_frag

  60 0   4 0 int       fs_minfree

  64 0   4 0 int       fs_rotdelay

  68 0   4 0 int       fs_rps

  72 0   4 0 int       fs_bmask

  76 0   4 0 int       fs_fmask

  80 0   4 0 int       fs_bshift

  84 0   4 0 int       fs_fshift

Maximum contiguous blocks and max number of blocks allocated 

to a single file within a cylinder group

  88 0   4 0 int       fs_maxcontig

  92 0   4 0 int       fs_maxbpg

  96 0   4 0 int       fs_fragshift

 100 0   4 0 int       fs_fsbtodb

 104 0   4 0 int       fs_sbsize

 108 0   4 0 int       fs_csmask

 112 0   4 0 int       fs_csshift

 116 0   4 0 int       fs_nindir

 120 0   4 0 int       fs_inopb

 124 0   4 0 int       fs_nspf

This file system's unique identifier number

 128 0   4 0 int       fs_id[0]

 132 0   4 0 int       fs_id[1]

Mirror state information for primary swap and "/" partitions

 136 0   0 4 u_int     fs_mirror.state.root

 136 4   0 1 u_int     fs_mirror.state.rflag

 136 5   0 4 u_int     fs_mirror.state.swap

 137 1   0 1 u_int     fs_mirror.state.sflag

 137 2   2 6 u_int     fs_mirror.state.spare

 140 0   4 0 int       fs_mirror.mirtime

 144 0   4 0 int       fs_featurebits

 148 0   4 0 int       fs_optim

Cylinder group summary array address, summary array size, 

cylinder group size

 152 0   4 0 int       fs_csaddr

 156 0   4 0 int       fs_cssize

 160 0   4 0 int       fs_cgsize

Number of tracks per cylinder group, sectors per track, 

sectors per cylinder, total number of cylinders in the file 

system, cylinders per group, and inodes per group

 164 0   4 0 int       fs_ntrak

 168 0   4 0 int       fs_nsect

 172 0   4 0 int       fs_spc

 176 0   4 0 int       fs_ncyl

 180 0   4 0 int       fs_cpg

 184 0   4 0 int       fs_ipg

 188 0   4 0 int       fs_fpg

Calculated cylinder group totals (this must be audited 

following a power failure)

 192 0   4 0 int       fs_cstotal.cs_ndir

 196 0   4 0 int       fs_cstotal.cs_nbfree

 200 0   4 0 int       fs_cstotal.cs_nifree

 204 0   4 0 int       fs_cstotal.cs_nffree

Next are the file system modification flag, the clean/dirty 

flag, the read-only flag, the spare flag (currently not used),

and a string holding the current mount point of the file 

system

 208 0   1 0 char      fs_fmod

 209 0   1 0 char      fs_clean

 210 0   1 0 char      fs_ronly

 211 0   1 0 char      fs_flags

 212 0 512 0 char[512] fs_fsmnt

 724 0   4 0 int       fs_cgrotor

 728 0   4 0 *         fs_csp

 732 0   4 0 int       fs_csp_pad

 736 0   4 0 int       fs_unused2[30]

 856 0   4 0 int       fs_cpc

 860 0   2 0 short     fs_postbl[32][8]

This file system's "magic number" (used to verify its type), 

its type name and pack name

1372 0   4 0 int       fs_magic

1376 0   6 0 char[6]   fs_fname

1382 0   6 0 char[6]   fs_fpack

1388 0   1 0 u_char    fs_rotbl[0]

The vnode

Next, we address the specifics of the vnode structure. We have learned that an inode contains all of a file's credentials and attributes, and is therefore the key to managing a file within a file system. The inode number is unique within the context of a single file system, and it is all that is needed to define a file. Within a kernel, there may be several file systems mounted together to create what appears to be a seamless, larger file system. Within this larger context, inode numbers are no longer guaranteed to be unique. Each mounted file system may have an inode 1, 2, and so on. To enable the kernel to refer to opened files with a unique handle, the virtual inode or vnode was created.

In a similar manner to the vfs structure, a vnode contains an operational array pointer to the kernel's type-specific routines for file manipulation tasks (see Figure 8-14).

The key fields of the vnode include a type number, a pointer to a type-specific operations array, and a reference to the in-core copy of the file's inode data. Listing 8.7 is an annotated listing of a virtual file system vnode:

Listing 8.7. q4> fields struct vnode

0 0 2 0 u_short v_flag

Shared lock count, exclusive lock count, private data count, 

and reference count

 2 0 2 0 u_short v_shlockc

 4 0 2 0 u_short v_exlockc

 6 0 2 0 u_short v_tcount

 8 0 4 0 int     v_count

Pointer to vfs structure if this is a mount point

12 0 4 0 *       v_vfsmountedhere

Pointers to the type specific vnode operations array, unix ipc

socket, stream head, and the vfs the file is in

16 0 4 0 *       v_op

20 0 4 0 *       v_socket

24 0 4 0 *       v_stream

28 0 4 0 *       v_vfsp

vnode type, device number, type-specific data (hfs inode, vxfs 

inode, rnode, ...), and parent file system type

32 0 4 0 enum4   v_type

36 0 4 0 int     v_rdev

40 0 4 0 *       v_data

44 0 4 0 enum4   v_fstype

Pointer to parent pseudo vas (if this maps to an executable 

image file)

48 0 4 0 *       v_vas

Beta semaphore locking structure

52 0 1 0 u_char  v_lock.b_lock

54 0 2 0 u_short v_lock.order

56 0 4 0 *       v_lock.owner

Mapped memory cache buffers for this file

60 0 4 0 *       v_cleanblkhd

64 0 4 0 *       v_dirtyblkhd

vnode write count, FS independent locks, soft hold count, and 

a copy of the va_nodeid

68 0 4 0 int     v_writecount

72 0 4 0 *       v_locklist

76 0 4 0 int     v_scount

80 0 4 0 int     v_nodeid

DNLC entry pointers if this vnode is currently described in 

the directory name lookup cache

84 0 4 0 *       v_ncachedhd

88 0 4 0 *       v_ncachevhd

92 0 4 0 *       v_pfdathd

96 0 4 0 u_int   v_last_fsync

The HFS In-Core inode Contains Its vnode

For an HFS file, the in-core inode structure includes the vnode structure and a complete copy of its disk-resident inode (the icommon structure we examined earlier) plus additional fields of information (Listing 8.8):

Listing 8.8. q4> fields struct inode

0 0  4 0 *         i_chain[0]

  4 0  4 0 *         i_chain[1]

The device number this inode came from

  8 0  4 0 int       i_dev

The inode number

 12 0  4 0 u_int     i_number

The state flags, lock word, and tid of last thread to lock this inode

 16 0  4 0 u_int     i_flag

 20 0  2 0 u_short   i_lockword

 24 0  4 0 int       i_tid

The virtual file system's vnode for the file is stored between offset 28 and 127

inode device pointer

128 0  4 0 *         i_devvp

132 0  4 0 int       i_diroff

Continuation inode pointer

136 0  4 0 *         i_contip

File system pointer

140 0  4 0 *         i_fs

Quota pointer

144 0  4 0 *         i_dquot

148 0  4 0 int       i_rdev

152 0  4 0 int       i_un.if_lastr

152 0  4 0 *         i_un.is_socket

156 0  4 0 *         i_fr.if_freef

160 0  4 0 *         i_fr.if_freeb

164 0  4 0 *         i_fselr.i_selp

168 0  2 0 short     i_fselr.i_selflag

172 0  4 0 *         i_fselw.i_selp

176 0  2 0 short     i_fselw.i_selflag

180 0  4 0 *         i_mount

Acopy of the disk-based inode (structure icommon) is stored between offset 184 and 311

Number of reader calls

312 0  2 0 u_short   i_rcount

Beta semaphore locking structures

316 0  1 0 u_char    i_b_sema.b_lock

318 0  2 0 u_short   i_b_sema.order

320 0  4 0 *         i_b_sema.owner

324 0  4 0 int       filler[0]

328 0  4 0 int       filler[1]

The relationship between the in-core inode data and the vnode varies between file system types, but the vnode structure itself is identical for all supported file systems. As the vnode uses operation's array pointers, it is up to the programmers of the referenced routines to have intimate knowledge of inode type-specific content.

When a file is opened by the kernel, it is identified by the device number of the volume on which the file system is located and its inode number. By using these two values, each file is guaranteed to have a unique identity within the scope of the operating system.

Caching inode / vnode Data in the Kernel

To improve system performance and reduce the amount of time spent accessing metadata on the disk, inode / vnode data is maintained in kernel-resident caches. Each type of file system is responsible for the allocation and maintenance of its inode / vnode cache. In most implementations caches are sized by kernel-tunable parameters or by an imbedded formula. A hash is formed using the device number and the inode number. Before a copy of an inode is read in from the physical disk, the inode cache is always checked to see if a copy of the data is present.

Smoke and Mirrors: Tying Together the File Subsystem Abstractions

Next, we need to tie the abstractions together into a seamless VFS implementation (see Figure 8-15).

Let's revisit our earlier scenario except that now /home is a separate file system mounted to the system's root file system. Again, our challenge is to follow the pathname /home/chris/stuff through the kernel's virtual structures.

We start our search by locating the kernel's copy of the / inode (2 on the first volume). The inode / vnode and root directory data of all mount points and file system roots are held in the caches and the buffer cache as long as a file system is mounted. To speed up this initial search, the kernel maintains a permanent shortcut pointer to the cached copy of the / inode / vnode in the symbol rootdir .

From this vnode , we determine the file system device number, and from the associated inode we get the data block pointer. These two numbers are used to hash our way into the buffer cache, where we find a copy of the root file system's root directory data. We take the inode number associated with the home directory and the device number to hash our way back into the inode cache for the next step of our search.

When we find the cached vnode for the /home directory (5 on the first volume), the v_vfsmountedhere pointer is valid and directs us to the kernel mount table and the vfs structure for the second mounted volume (did you ever play the children's game Chutes and Ladders?). We then follow the v_data pointer to find the root inode / vnode (2 on the second volume) and cached data block for the mounted /home file system.

We continue our search within the /home file system, locating the inode / vnode (10 on the second volume) and cached data for the /home/chris directory and finally the inode / vnode (14 on the second volume) and cached data for the /home/chris/stuff file. Accessing these last two stops on our search may or may not find the requested data in the appropriate caches. If they aren't loaded, then the system uses the routines referenced by the operational arrays and kernel functions to load copies from the disk into the caches.

This brings us to the end of our quest. Next we consider the attachment of an open file to a process.

Connecting an Open File to a Process

We have seen that the proc structure is the base of all process- related kernel structures. The definition of a process's resources includes mapping opened files to per-process file descriptors (see Figure 8-16).

From the kernel's point of view, each distinct file open() call must be tracked, which is accomplished by making entries in the system file table. From the process's point of view, it is only concerned with its own file descriptors, but the kernel must manage all open() calls.

The number of file descriptors a single process may have is controlled by the kernel-tunable parameters max_files (for a regular user process) and max_files_lim (for a superuser process), and may be set up to 60,000. The default is 60 and is usually sufficient, considering that most processes only need to map stdin , stdout , and stderr .

To avoid wasting kernel memory space, process file descriptors are stored in blocks of eight for HP-UX 11.11 (HP-UX 11.0 used 32 descriptors per block), and the blocks are referenced through a partition table pointed to by the proc structure. Additional blocks are allocated as needed by the kernel.

On HP-UX 11.11 the file_descriptor_t structure contained:

fd_lock       a spinlock structure

*fd_filep     a pointer to a system file table file entry

fd_locker_tid a reference to a locking thread

fd_state      the current descriptor state

fd_pofile     reference to the ofile partition entry

The kernel file system table consists of nfile entries (kernel-tunable) of type file . See Listings 8.9 and 8.10.

Listing 8.9. q4> fields struct file

The file descriptor table flags are:

  0 0 4 0 int       f_flag

The kernel object represented by this entry

  4 0 2 0 short     f_type

link count from the message queue

   6 0 2 0 short     f_msgcount

reference count

   8 0 4 0 int       f_count

type-specific file system operations array pointer

  12 0 4 0 *         f_ops

pointer to this file's vnode/socket kernel data

  16 0 4 0 *         f_data

  20 0 4 0 int       f_freeindex

  24 0 8 0 long long f_offset

  32 0 4 0 *         f_buf

credentials of user who opened the file

  36 0 4 0 *         f_cred

kernel beta-semaphore

  40 0 1 0 u_char    f_b_sema.b_lock

  42 0 2 0 u_short   f_b_sema.order

  44 0 4 0 *         f_b_sema.owner

data intercept audit flag

  48 0 2 0 short     f_tap

Listing 8.10. q4> fields struct fileops

0 0 4 0 * fo_rw

 4 0 4 0 * fo_ioctl

 8 0 4 0 * fo_select

12 0 4 0 * fo_close

The Buffer Cache

Just as the kernel keeps copies of open inode data in a cache, it also maintains a much larger cache of recently accessed file data blocks (or extents, depending on the type of file system). This buffer cache is a key component of the HP-UX operating system. Figure 8-17 provides an overview of the buffer cache design.

A basic premise of the UNIX operating system is that every thing is a file. This model serves many purposes and greatly reduces the overall complexity of the operating system. With this in mind, it is understandable that everything that may be done to improve file performance provides a large payback.

Being Flexible: The Dynamic Buffer Cache

The HP-UX implementation of a buffer cache follows a dynamic model. The buffer cache is mapped into the kernel's address space, but the physical pages allocated to it come from the same available memory pools as those used for user processes. In this manner, the buffer cache competes with user code for system memory resources.

The kernel allows the administrator to set a maximum and minimum percentage of the available memory that may be allocated for buffer cache use. Remember that available memory means the amount of physical memory remaining after the kernel allocates pages for its exclusive use during system initialization. The kernel-tunable parameters to enable a dynamic buffer cache are:

• dbc_min_pct : Minimum percentage of available memory that may be allocated for buffer cache use

• dbc_max_pct : Maximum percentage of available memory pages that may be allocated for buffer cache use

If the dbc_min_pct is set equal to or larger than the dbc_max_pct , then the dynamic buffer cache is capped at the size dictated by dbc_min_pct . This presents what at first seems to be a conundrum . How can it be a dynamic buffer cache if the size is fixed? While the size is fixed, it is simply a targeted value and not an absolute. As long as the buffer cache is considered to be dynamic, its pages may be aged and stolen by the vhand daemon during times of heavy memory pressure. This means that while the overall size appears to be static, the specific pages allocated to the cache may change from time to time, so they are considered dynamic.

If these two dynamic tunables are not set, then the following older kernel parameters take effect and the cache is flagged as static; that is, pages once allocated to the cache remain there and vhand cannot scan them.

• nbuf : Number of buffer headers

• bufpages : Number of buffer pages

Once a buffer has been populated with a copy of file data, the kernel needs an efficient method to search for it in the cache. This is accomplished through the use of a hash (by now you expected this, didn't you!).

The Buffer Cache Hash

Figure 8-18 illustrates the basic design of the buffer cache. Individual buffers are pointed to by buffer headers' which are arranged in hash chains. In the case of a read() , the hash offset is calculated using the device number and block offset (obtained from the vnode ) for the requested disk data.

Once the hash has been calculated, the appropriate hash chain is searched to see if the requested data is present in the cache. In the case of a miss , the kernel works with the appropriate hardware driver, requests a physical data transfer from the disk, and allocates a free cache buffer to store the data in. Requests made and satisfied by the buffer cache are said to be logical reads and writes. Reads and writes between the buffer cache and a disk are called physical .

A write() request is handled in a similar manner. If a buffer has already been started, a simple logical write is performed. When a buffer is filled or when a dirty buffer (one whose content differs from its counterpart on the disk) is found by the sync daemon during one of its scheduled scans , a physical write is scheduled. Physical writes may also be specifically requested by a programmer or when a file is closed.

Listings 8.11 and 8.12 show selected fields from q4 listings of the buffer header and buffer structure.

Listing 8.11. q4> fields struct bufhd

The buffer header state flag

   0 0 4 0 int b_flags

Forward/backward linkage pointers for the hash chain

   4 0 4 0 *   b_forw

   8 0 4 0 *   b_back

Modification timestamp

  12 0 4 0 int b_checkdup

Lock structure for this buffer hash chain

  16 0 4 0 *   bh_lock

Listing 8.12. q4> fields struct buf (a partial listing)

The buffer state flags

  0 0 4 0 int                b_flags

Linkage pointers connecting a buffer to a hash chain

    4 0 4 0 *                  b_forw

    8 0 4 0 *                  b_back

Linkage pointer connecting a buffer to a free list

   12 0 4 0 *                  av_forw

   16 0 4 0 *                  av_back

Linkage pointers connecting a buffer to a vnodes clean/dirty list

   20 0 4 0 *                  b_blockf

   24 0 4 0 *                  b_blockb

   28 0 4 0 *                  b_strategy

   32 0 4 0 *                  b_un.b_addr

   32 0 4 0 *                  b_un.b_words

   32 0 4 0 *                  b_un.b_filsys

   32 0 4 0 *                  b_un.b_cs

   32 0 4 0 *                  b_un.b_cg

   32 0 4 0 *                  b_un.b_dino

   32 0 4 0 *                  b_un.b_daddr

   36 0 4 0 int                b_un2.b_sectno

   36 0 4 0 int                b_un2.b_byteno

   40 0 4 0 int                b_dev

   44 0 4 0 int                b_blkno

   48 0 4 0 *                  b_sc

The count of how many times this buffer has been returned to a 

free list since it was allocated

   52 0 4 0 int                b_bcount

   56 0 2 0 u_short            b2_flags

Error number (if B_ERROR is set in b_flags), buffer size, and offset

   58 0 2 0 short              b_error

   60 0 4 0 int                b_bufsize

   64 0 4 0 int                b_offset

   68 0 4 0 *                  b_merge

The pointer contains the address of the routine to call when a 

pending I/O is finished

   72 0 4 0 *                  b_iodone

---------------------------------------

Each nc_hash[] array element contains two linkage pointers

   0 0 4 0 * hash_next

   4 0 4 0 * hash_prev

First the entry is linked to its hash chain

   0 0  4 0 *        hash_next

   4 0  4 0 *        hash_prev

All entries are linked into a least recently used list

   8 0  4 0 *        lru_next

  12 0  4 0 *        lru_prev

This points to the directory's vnode

  16 0  4 0 *        vp

And a pointer to the parent directory's vnode

  20 0  4 0 *        dp

The entry's length, name, and credentials are stored next

  24 0  1 0 char     namlen

  25 0 39 0 char[39] name

  64 0  4 0 *        cred

Mount point directories are linked to the virtual file system table

  68 0  4 0 *        vfs_next

  72 0  4 0 *        vfs_prev

All entries sharing a parent directory are dual linked

  76 0  4 0 *        dp_next

  80 0  4 0 *        dp_prev

All entries sharing a vnode are dual linked

  84 0  4 0 *        vp_next

  88 0  4 0 *        vp_prev