The Linux RAID-1, 4, 5 Code

The MD mapping function works fine for re-mapping personalities such as the linear and the striping personalities. Unfortunately, it is not enough to support the RAID-1, RAID-4 and RAID-5 personalities. The reason for this is that these modes cannot do their job by just re-mapping a given device/sector pair into new device/sector pairs; all of these new personalities require complex input/output operations to fulfill a single request.

For example, the mirroring personality (RAID-1) duplicates the information onto all of the disks in the array, so that the information on each disk is identical. The size of the disk array is the size of the smallest disk (the lowest common denominator). Therefore, it is not a good idea to make a RAID-1 with a 100MB disk and a 1GB disk, since the driver will just provide 100MB on each (and ignore the fact that you have 900MB free on the second disk).

The MD driver, when asked to write information to the device, queues a write request for all of the devices in the array with the same information. The system can continue operation regularly with all of the remaining devices (usually, just one extra device). With mirroring in place, read requests are balanced among the devices in the array. If any of the devices fail, the device driver marks it as non-operational and stops using it; the driver will continue working with the remaining disks as if nothing had happened. Figure 2 shows how this mode can be used; shadowed regions represent the redundant information.

Next we have the more complex block-interleaved parity (RAID-4) and block-interleaved distributed-parity (RAID-5) personalities. A striping unit is a set of contiguous sectors. Both the RAID-4 and RAID-5 personalities use one stripe on one of the disks in the array to store the parity information and use the remaining stripes for data.

Whenever one of the data sectors is modified, the parity sector has to be recomputed and written back to the disk. To recompute the parity sector, the device driver has to read the contents of the old parity block and recompute the new parity information. Then it writes the new contents of the data and the parity block.

The difference between RAID-4 and RAID-5 is that the former stores the parity information in a fixed device (the last one of the composing devices in our implementation), while the latter distributes the parity blocks between the composing devices.

Figure 3 shows the RAID-4 arrangement; shadowed regions are the redundant information, which in this case are the parity blocks. RAID-4 has a bottleneck due to the parity disk, since all MD activity depends on the parity bit disk to finish its operation.

Figure 4 shows the RAID-5 arrangement; shadowed regions are the redundant information (the parity blocks once again), and each disk here represents a striping unit. In RAID-5, the RAID-4 bottleneck is eliminated by distributing the work among several disks.

In the case of a disk failure while using the RAID-4 or RAID-5 personalities, the disk array can continue operation since it has enough information to reconstruct any lost disk. The MD device is slower at this point; every access to a data sector in the lost disk requires reading the information from all the sectors in the same stripe as well as the parity bit and computing the contents of the original sector based on this information.

The new personalities, as we have implemented them require a change to the ll_rw_blk routine and some extra code in the input/output end-request notification code in the kernel.

The ll_rw_blk routine is modified to make a call to the md_make_request instead of calling the kernel's make_request when the blocks are scheduled to be sent to an MD device. The md_make_request routine in turn calls the request-making routine once for each personality to carry out its job. In the case of RAID-0 and the linear modes, md_make_request calls the regular make_request routine.

The ll_rw_blk routine in the presence of the new MD driver is shown here:

ll_rw_blk (blocks)
{
    sanity-checks ();
    for-each block in blocks {
        if (block is md-device)
            md_map (block)
    }
    for-each block in blocks {
        if (request-is-for (raid1,raid4,raid5))
            md_make_request (block);
        else
            make_request (block);
    }
}

Because of the increased complexity and error recovery capabilities of the new RAID code, the personality code must be informed of the results of its input/output operations. If a disk fails it must mark the disk as non-operational, and in the case of the RAID-4 and RAID-5 code, it must move between the different phases of the process. We modified the kernel input/output end-request routines to call the RAID personality's end_request routine to deal with the results.

A typical end_request routine is as follows:

raidx_end_request (buffer_head, uptodate)
{
    if (!uptodate)
        md_error (buffer_head)
    if (buffer_head->cmd is READ){
        if (uptodate){
            raidn_end_buffer_io (buffer_head,
                uptodate)
            return;
        /* read error */
        raid_reschedule_retry (buffer_head);
    }
    /* write case */
    if (finished-with buffer_head)
        raidn_end_buffer_io (buffer_head,
                uptodate)
}