When a block device file is being opened, the kernel must determine whether the device file is already open. In fact, if the file is already open, the kernel must not initialize the corresponding block device driver.

This problem is as easy as it appears at first look. On the one hand, we stated in the earlier section Section 13.2 that block device files that have the same major number are usually associated with the same block device driver. However, each block device driver that handles more than one minor number can be considered several specialized block device drivers, so this case doesn’t create problems. In the rest of this section, when we use the term “block device driver,” we mean the kernel layer that handles I/O data transfers from/to a hardware device specified by both a major number and a minor number.

A real complication, however, is that block device files that have the same major and minor numbers but different pathnames are regarded by the VFS as different files, but they really refer to the same block device driver. Therefore, the kernel cannot determine whether a block device driver is already in use by simply checking for the existence in the inode cache of an object for the block device file.

To keep track of which block device drivers are currently in use, the kernel uses a hash table indexed by the major and minor numbers. Every time a block device driver is being used, the kernel checks whether the corresponding block device driver identified by the major and minor numbers is already stored in the hash table. If so, the block device driver is already in use; notice that the hash function works on the major and minor numbers of the block device file, thus it doesn’t matter whether the block device driver was previously activated by accessing a given block device file, or another one that has the same major and minor numbers. Conversely, if a block device driver associated with the given major and minor numbers is not found, the kernel inserts a new element into the hash table.

The hash table array is stored in bdev_hashtable variable; it includes 64 lists of block device descriptors. Each descriptor is a block_device data structure whose fields are shown in Table 13-4.

The bd_inodes field of the block device descriptor stores the head (the first dummy element) of a doubly linked circular list of inodes relative to opened block device files that refer to the block device driver. The i_devices field of the inode object stores the pointers for the previous and next element in this list.

Each block device descriptor stores in the bd_inode field the address of a special block device inode object for the driver. This inode doesn’t correspond to a disk file; rather, it belongs to the bdev special filesystem (see Section 12.3.1). Essentially, the block device inode stores the “master copy” of the information shared by all inode objects of the block device files that refer to the same block device.

Let’s now describe how a block device driver is initialized. We already described how the kernel customizes the methods of the file object when a block device file is opened in Section 13.2.3. Its f_op field is set to the address of the def_blk_fops variable. The contents of this table are shown in Table 13-5. The dentry_open( ) function checks whether the open method is defined; this is always true for a block device file, so the blkdev_open( ) function is executed.

This function checks whether the block device driver is already in use:

bd_acquire(inode);
do_open(inode->i_bdev, filp);

The bd_acquire( ) function essentially executes the following operations:

Next, blkdev_open( ) invokes do_open( ), which executes the following main steps:

The open method of the block device driver descriptor can further customize the methods of the block device driver, allocate resources, and take other measures based on the minor number of the block device file.

Among other things, the device driver initialization function must determine the size of the physical block device corresponding to the device file. This length, represented in 1,024-byte units, is stored in the blk_size global array indexed by both the major and minor number of the device file.

Each data transfer operation for a block device acts on a group of adjacent bytes called a sector . In most disk devices, the size of a sector is 512 bytes, although there are devices that use larger sectors (1,024 and 2,048 bytes). Notice that the sector should be considered the basic unit of data transfer; it is never possible to transfer less than a sector, although most disk devices are capable of transferring several adjacent sectors at once.

The kernel stores the sector size of each hardware block device in a table named hardsect_size. Each element in the table is indexed by the major number and the minor number of the corresponding block device file. Thus, hardsect_size[3][2] represents the sector size of /dev/hda2, which is the second primary partition of the first IDE disk (see Table 13-2). If hardsect_size[ maj ] is NULL, all block devices sharing the major number maj have a standard sector size of 512 bytes.

Block device drivers transfer a large number of adjacent bytes called a block in a single operation. A block should not be confused with a sector. The sector is the basic unit of data transfer for the hardware device, while the block is simply a group of adjacent bytes involved in an I/O operation requested by a device driver.

In Linux, the block size must be a power of 2 and cannot be larger than a page frame. Moreover, it must be a multiple of the sector size, since each block must include an integral number of sectors. Therefore, on PC architecture, the permitted block sizes are 512, 1,024, 2,048, and 4,096 bytes. The same block device driver may operate with several block sizes, since it has to handle a set of device files sharing the same major number, while each block device file has its own predefined block size. For instance, a block device driver could handle a hard disk with two partitions containing an Ext2 filesystem and a swap area (see Chapter 16 and Chapter 17). In this case, the device driver uses two different block sizes: 1,024 bytes for the Ext2 partition and 4,096 bytes for the swap partition.

The kernel stores the block size in a table named blksize_size; each element in the table is indexed by the major number and the minor number of the corresponding block device file. If blksize_size[ maj ] is NULL, all block devices sharing the major number maj have a standard block size of 1,024 bytes. (You should not confuse blk_size with the blksize_size array, which stores the block size of the block devices rather than the size of the block device themselves.)

Each block requires its own buffer , which is a RAM memory area used by the kernel to store the block’s content. When a device driver reads a block from disk, it fills the corresponding buffer with the values obtained from the hardware device; similarly, when a device driver writes a block on disk, it updates the corresponding group of adjacent bytes on the hardware device with the actual values of the associated buffer. The size of a buffer always matches the size of the corresponding block.

The buffer head is a descriptor of type buffer_head associated with each buffer. It contains all the information needed by the kernel to know how to handle the buffer; thus, before operating on each buffer, the kernel checks its buffer head.

The buffer head fields are listed in Table 13-6. The b_data field of each buffer head stores the starting address of the corresponding buffer. Since a page frame may store several buffers, the b_this_page field points to the buffer head of the next buffer in the page. This field facilitates the storage and retrieval of entire page frames (see Section 13.4.8.2 later in this chapter). The b_blocknr field stores the logical block number (i.e., the index of the block inside the disk partition).

The b_state field stores the following flags:

The b_dev field identifies the virtual device containing the block stored in the buffer, while the b_rdev field identifies the real device. This distinction, which is meaningless for simple hard disks, has been introduced to model Redundant Array of Independent Disks (RAID) storage units consisting of several disks operating in parallel. For reasons of safety and efficiency, files stored in a RAID array are scattered across several disks that the applications think of as a single logical disk. Besides the b_blocknr field representing the logical block number, it is necessary to specify the specific disk unit in the b_rdev field and the corresponding sector number in the b_rsector field.

Although block device drivers are able to transfer a single block at a time, the kernel does not perform an individual I/O operation for each block to be accessed on disk; this would lead to poor disk performances, since locating the physical position of a block on the disk surface is quite time-consuming. Instead, the kernel tries, whenever possible, to cluster several blocks and handle them as a whole, thus reducing the average number of head movements.

When a process, the VFS layer, or any other kernel component wishes to read or write a disk block, it actually creates a block device request . That request essentially describes the requested block and the kind of operation to be performed on it (read or write). However, the kernel does not satisfy a request as soon as it is created—the I/O operation is just scheduled and will be performed at a later time. This artificial delay is paradoxically the crucial mechanism for boosting the performance of block devices. When a new block data transfer is requested, the kernel checks whether it can be satisfied by slightly enlarging a previous request that is still waiting (i.e., whether the new request can be satisfied without further seek operations). Since disks tend to be accessed sequentially, this simple mechanism is very effective.

Deferring requests complicates block device handling. For instance, suppose a process opens a regular file and, consequently, a filesystem driver wants to read the corresponding inode from disk. The block device driver puts the request on a queue and the process is suspended until the block storing the inode is transferred. However, the block device driver itself cannot be blocked because any other process trying to access the same disk would be blocked as well.

To keep the block device driver from being suspended, each I/O operation is processed asynchronously. Thus, no kernel control path is forced to wait until a data transfer completes. In particular, block device drivers are interrupt-driven (see Section 13.4.5.2 earlier in this chapter): a high-level driver creates a new block device request or enlarges an already existing block device request and then terminates. A low-level driver , which is activated at a later time, invokes a so-called strategy routine , which takes the request from a queue and satisfies it by issuing suitable commands to the disk controller. When the I/O operation terminates, the disk controller raises an interrupt and the corresponding handler invokes the strategy routine again, if necessary, to process another request in the queue.

Each block device driver maintains its own request queues ; there should be one request queue for each physical block device, so that the requests can be ordered in such a way as to increase disk performance. The strategy routine can thus sequentially scan the queue and service all requests with the minimum number of head movements.

Request descriptors

Each block device request is represented by a request descriptor , which is stored in the request data structure illustrated in Table 13-7. The direction of the data transfer is stored in the cmd field; it is either READ (from block device to RAM) or WRITE (from RAM to block device). The rq_status field is used to specify the status of the request; for most block devices, it is simply set either to RQ_INACTIVE (for a request descriptor not in use) or to RQ_ACTIVE (for a valid request that is to be serviced or is already being serviced by the low-level driver).

Table 13-7. The fields of a request descriptor

Type	Field	Description
struct list_head	queue	Pointers for request queue list
int	elevator_sequence	The “age” of the request for the elevator algorithm
volatile int	rq_status	Request status
kdev_t	rq_dev	Device identifier
int	cmd	Requested operation
int	errors	Success or failure code
unsigned long	sector	First sector number on the (virtual) block device
unsigned long	nr_sectors	Number of sectors of the request on the (virtual) block device
unsigned long	hard_sector	First sector number of the (real) block device
unsigned long	hard_nr_sectors	Number of sectors of the request on the (real) block device
unsigned int	nr_segments	Number of segments in the request on the (virtual) block device
unsigned int	nr_hw_segments	Number of segments in the request on the (real) block device
unsigned long	current_nr_sectors	Number of sectors in the block currently transferred
void *	special	Used only by drivers of SCSI devices
char *	buffer	Memory area for I/O transfer
struct completion *	waiting	Wait queue associated with request
struct buffer_head *	bh	First buffer descriptor of the request
struct buffer_head *	bhtail	Last buffer descriptor of the request
request_queue_t *	q	Pointer to request queue descriptor

The request may encompass many adjacent blocks on the same device. The rq_dev field identifies the block device, while the sector field specifies the number of the first sector of the first block in the request. The nr_sector field specifies the number of sectors in the request yet to be transferred. The current_nr_sector field stores the number of sectors in first block of the request. As we’ll later see in Section 13.4.7, the sector, nr_sector, and current_nr_sector fields could be dynamically updated while the request is being serviced.

The nr_segments field store the number of segments in the request. Although all blocks in the requests must be adjacent on the block device, their corresponding buffers are not necessarily contiguous in RAM. A segment is a sequence of adjacent blocks in the request whose corresponding buffers are also contiguous in memory. Of course, a low-level device driver could program the DMA controller so as to transfer all blocks in the same segment in a single operation.

The hard_sector, hard_nr_sectors, and nr_hw_segments fields usually have the same value as the sector, nr_sectors, and nr_segments fields, respectively. They differ, however, when the request refers to a driver that handles several physical block devices at once. A typical example of such a driver is the Logical Volume Manager (LVM), which is able to handle several disks and disk partitions as a single virtual disk partition. In this case, the two series of fields differ because the former refers to the real physical block device, while the latter refers to the virtual device. Another example is software RAID, a driver that duplicates data on several disks to enhance reliability.

All buffer heads of the blocks in the request are collected in a simply linked list. The b_reqnext field of each buffer head points to the next element in the list, while the bh and bhtail fields of the request descriptor point, respectively, to the first element and the last element in the list.

The buffer field of the request descriptor points to the memory area used for the actual data transfer. If the request involves a single block, buffer is just a copy of the b_data field of the buffer head. However, if the request encompasses several blocks whose buffers are not consecutive in memory, the buffers are linked through the b_reqnext fields of their buffer heads as shown in Figure 13-3. On a read, the low-level driver could choose to allocate a large memory area referred by buffer, read all sectors of the request at once, and then copy the data into the various buffers. Similarly, for a write, the low-level device driver could copy the data from many nonconsecutive buffers into a single memory area referred by buffer and then perform the whole data transfer at once.

Figure 13-3. A request descriptor and its buffers and sectors

Figure 13-3 illustrates a request descriptor encompassing three blocks. The buffers of two of them are consecutive in RAM, while the third buffer is by itself. The corresponding buffer heads identify the logical blocks on the block device; the blocks must necessarily be adjacent. Each logical block includes two sectors. The sector field of the request descriptor points to the first sector of the first block on disk, and the b_reqnext field of each buffer head points to the next buffer head.

During the initialization phase, each block device driver usually allocates a fixed number of request descriptors to handle its forthcoming I/O requests. The blk_init_queue( ) function sets up two equally sized lists of free request descriptors: one for the READ operation and another for the WRITE operations. The size of these lists is set to 64 if the RAM size is greater than 32 MB, or to 32 if the RAM size is less than or equal to 32 MB. The status of all request descriptors is set initially to RQ_INACTIVE.

The fixed number of request descriptors may become, under very heavy loads and high disk activity, a bottleneck. A dearth of free descriptors may force processes to wait until an ongoing data transfer terminates. Thus, a wait queue is used to queue processes waiting for a free request element. The get_request_wait( ) tries to get a free request descriptor and puts the current process to sleep in the wait queue if none is found; the get_request( ) function is similar but simply returns NULL if no free request descriptor is available.

A threshold value known as batch_requests (set to 32 or to 16, depending on the RAM size) is used to cut down kernel overhead; when releasing a request descriptor, processes waiting for free request descriptors are not woken up unless there are at least batch_requests free descriptors. Conversely, when looking for a free request descriptor, get_request_wait( ) relinquishes the CPU if there are fewer than batch_requests free descriptors.

The ll_rw_block( ) function creates a block device request. It is invoked from several places in the kernel to trigger the I/O data transfer of one or more blocks. The function receives the following parameters:

The buffer heads were previously initialized, so each specifies the block number, the block size, and the virtual device identifier (see the earlier section Section 13.4.4).

The function performs the following actions:

The generic_make_request( ) function posts the request to the low-level driver. It receives as parameters the buffer head bh and the type of operation rw (READ, WRITE, or READA), and performs the following operations:

In most cases, block device drivers implement the make_request_fn method with the _ _make_request( ) function. It receives as parameters the queue descriptor, the buffer head bh, and the type of operation rw, and performs the following operations:

We have now reached the lowest level in Linux’s block device handling. This level is implemented by the strategy routine, which interacts with the physical block device to satisfy the requests collected in the queue.

As mentioned earlier, the strategy routine is usually started after inserting a new request in an empty request queue. Once activated, the low-level driver should handle all requests in the queue and terminate when the queue is empty.

A naïve implementation of the strategy routine could be the following: for each element in the queue, interact with the block device controller to service the request and wait until the data transfer completes. Then remove the serviced request from the queue and proceed with the next one.

Such an implementation is not very efficient. Even assuming that data can be transferred using DMA, the strategy routine must suspend itself while waiting for I/O completion; hence, an unrelated user process would be heavily penalized. (The strategy routine does not necessarily execute on behalf of the process that has requested the I/O operation but at a random, later time, since it is activated by means of the tq _disk task queue.)

Therefore, many low-level drivers adopt the following strategy:

Basically, low-level drivers can be further classified into the following:

Drivers of the second type are much more complicated to design and implement than drivers of the first type. Indeed, although the sectors are adjacent on the physical block devices, the buffers in RAM are not necessarily consecutive. Therefore, any such driver may have to allocate a temporary area for the DMA data transfer, and then perform a memory-to-memory copy of the data between the temporary area and each buffer in the request’s list.

Since requests handled by both types of drivers consist of adjacent blocks, disk performance is enhanced because fewer seek commands are issued. However, the second type of drivers do not further reduce the number of seek commands, so transferring several blocks from disk together is not as effective in boosting disk performance.

The kernel doesn’t offer any support for the second type of drivers: they must handle the request queues and the buffer head lists on their own. The choice to leave the job up to the driver is not capricious or lazy. Each physical block device is inherently different from all others (for example, a floppy driver groups blocks in disk tracks and transfers a whole track in a single I/O operation), so making general assumptions on how to service each clustered request makes very little sense.

However, the kernel offers a limited degree of support for the low-level drivers in the first class. We’ll spend a little more time describing such drivers.

A typical strategy routine should perform the following actions:

The interrupt handler associated with the termination of the DMA data transfer for the block device should invoke (either directly or via a bottom half) the end_request function (or a custom function of the block device driver that does the same things). The function, which receives as parameters the value 1 if the data transfer succeeds or the value 0 if an error occurrs, performs the following operations:

After invoking end_request, the low-level driver checks whether the request queue is empty. If it is not, the strategy routine is executed again. Notice that end_request actually performs two nested iterations: the outer one on the elements of the request queue and the inner one on the elements in the buffer head list of each request. The strategy routine is thus invoked once for each block in the request queue.

We’ll discuss in the forthcoming chapters how the kernel uses the block device drivers. We’ll see that there are a number of cases in which the kernel activates disk I/O data transfers. However, let’s describe here the two fundamental kinds of I/O data transfer for block devices:

Block I/O operations are most often used when the kernel reads or writes single blocks in a filesystem (for example, a block containing an inode or a superblock). Conversely, page I/O operations are used mainly for reading and writing files (both regular files and block device files), for accessing files through the memory mapping, and for swapping.

Both kinds of I/O operations rely on the same functions to access a block device, but the kernel uses different algorithms and buffering techniques with them.