DMA controller of a RAID storage controller with integrated XOR parity computation capability adapted to compute parity in parallel with the transfer of data segments

Claim 2

In a DMA controller of a RAID storage controller in a RAID storage subsystem, a method to compute parity comprising the steps of: transferring a data portion of a stripe from a host system to a RAID storage subsystem through said DMA controller from a random access source memory to a destination memory, wherein said data portion of said stripe is comprised of a plurality of data blocks wherein each of said plurality of data blocks is comprised of a plurality of data segments, and wherein said plurality of data segments are stored in said source memory in a first predetermined order and wherein said data segments are transferred to said destination memory in a second predetermined order different from said first predetermined order; and computing, within said DMA controller, a plurality of XOR parity segments corresponding to said plurality of data segments, wherein the step of transferring a data portion of a stripe further comprises the steps of: a) transferring a first data segment of said plurality of data segments of a data block of said plurality of data blocks of said stripe; b) transferring a corresponding data segment of said plurality of data segments of a next data block of said plurality of data blocks; c) storing XOR parity generated by said computing step in a buffer; d) repeating steps b) and c) for each data block of said stripe until each corresponding data segment of each block of said plurality of data blocks of said stripe have been transferred; and e) repeating steps a) through d) for a next data segment of said plurality of data segments in each of said plurality of blocks in said data portion of said stripe until all of said plurality of data segments have been transferred, and wherein the computing step is performed substantially simultaneously with said step of transferring.

Claim 3

The method of claim 1 further comprising the step of: storing each of said plurality of XOR parity segments in said destination memory.

Claim 4

The method of claim 1 wherein said buffer is a FIFO for XOR parity accumulation and wherein the step of transferring said plurality of data segments further comprises the steps of: a) resetting said FIFO to all zeros; b) transferring a data segment of said plurality of data segments of a data block of said plurality of data blocks; c) storing XOR parity generated by said computing step in said FIFO; d) repeating steps b) and c) for each data block of said plurality of data blocks of said stripe until each corresponding data segment of each data block of said plurality of data blocks of said stripe have been transferred; e) repeating steps a) through d) for a next data segment of said plurality of data segments in each of said plurality of blocks in said data portion of said stripe until all of said plurality of data segments have been transferred.

Claim 5

The method of claim 1 wherein said buffer is a FIFO for XOR parity accumulation and wherein approximately equal in size to the size of one of said plurality of data segments and wherein said step of transferring a plurality of data segments includes the step of: reading said data segments from said source memory in a predetermined order operable to compute XOR parity of corresponding segments of said data portion of said stripe substantially in parallel with the transfer of said plurality of data segments.

Claim 6

The method of claim 1 further comprising a storage subsystem including a plurality of disk drives and is operating in a degraded mode having at least one non-functional disk drive with corresponding missing data segments from said plurality of data segments, and wherein the step of transferring includes the steps of: transferring said plurality of data segments, wherein said transfer is devoid of said missing data segments; and transferring previously computed associated parity segments, and wherein the step of computing a plurality of XOR parity segments comprises the step of: computing a plurality of XOR parity segments representative of said missing data segments.

Claim 7

A DMA controller for computing XOR parity in a RAID storage subsystem comprising: DMA transfer means for transferring a data portion of a stripe from a random access source memory to a destination memory in a predetermined order different than the order in which said stripe is stored in said source memory; a FIFO for storing parity values generated in said DMA controller; XOR generation means coupled to said FIFO; and XOR buffer circuit coupled to said DMA transfer means for capturing said stripe as it is transferred by said DMA transfer means wherein said circuit is operable to control said FIFO and said XOR generation means in response to transfer of said stripe by said DMA transfer means, wherein said stripe is comprised of a plurality of blocks and wherein each block is comprised of a plurality of segments, and wherein said DMA transfer means further comprises: means for transferring a first data segment of said plurality of data segments of a data block of said plurality of data blocks of said stripe; means for transferring a corresponding data segment of said plurality of data segments of a next data block of said plurality of data blocks; means for storing XOR parity generated by said XOR buffer circuit; first means for repeating operation of said means for transferring a corresponding data segment and operation of said means for storing for each data block of said stripe until each corresponding data segment of each block of said plurality of data blocks of said stripe have been transferred; and first means for repeating operation of said means for transferring a first data segment and operation of said means for transferring a corresponding data segment and operation of said means for storing and operation of said means for repeating for a next data segment of said plurality of data segments in each of said plurality of blocks in said data portion of said stripe until all of said plurality of data segments have been transferred.

Claim 8

A DMA controller for computing XOR parity in a RAID storage subsystem comprising: DMA transfer means for transferring a data portion of a stripe from a random access source memory to a destination memory in a predetermined order different than the order in which said stripe is stored in said source memory; a FIFO for storing parity values generated in said DMA controller; XOR generation means coupled to said FIFO; and XOR buffer circuit coupled to said DMA transfer means for capturing said stripe as it is transferred by said DMA transfer means wherein said circuit is operable to control said FIFO and said XOR generation means in response to transfer of said stripe by said DMA transfer means, wherein said stripe is comprised of a plurality of blocks and wherein each block is comprised of a plurality of segments, and wherein said DMA transfer means further comprises: means for transferring a first data segment of said plurality of data segments of a data block of said plurality of data blocks of said stripe; means for transferring a corresponding data segment of said plurality of data segments of a next data block of said plurality of data blocks; means for storing XOR parity generated by said XOR buffer circuit; first means for repeating operation of said means for transferring a corresponding data segment and operation of said means for storing for each data block of said stripe until each corresponding data segment of each block of said plurality of data blocks of said stripe have been transferred; and first means for repeating operation of said means for transferring a first data segment and operation of said means for transferring a corresponding data segment and operation of said means for storing and operation of said means for repeating for a next data segment of said plurality of data segments in each of said plurality of blocks in said data portion of said stripe until all of said plurality of data segments have been transferred.

Claim 9

The DMA controller of claim 6 wherein said XOR buffer circuit includes: first means for controlling said memory to store data captured during transfer of said plurality of data segments in said memory; second means for controlling said memory and said XOR generation means to compute the bitwise XOR of data previously stored in said memory and data captured during transfer of said plurality of data segments and to store said bitwise XOR result in said memory; and third means for controlling said memory to read the contents of said memory for purposes of transferring parity data from said memory to said destination memory.

Claim 10

A DMA controller for use in a RAID storage controller of a RAID storage subsystem, said DMA controller comprising: means for transferring a data portion of a stripe through said DMA controller from a random access source memory to a destination memory, wherein said stripe is stored in a predetermined first order in said source memory and wherein said stripe is transferred to said destination memory in a predetermined second order different from said predetermined first order; and means for computing, within said DMA controller, a plurality of XOR parity segments corresponding to said stripe, wherein said means for computing and said means for transferring are operable substantially simultaneously, wherein said stripe is comprised of a plurality of blocks and wherein each block is comprised of a plurality of segments, and wherein said means for transferring further comprises: means for transferring a first data segment of said plurality of data segments of a data block of said plurality of data blocks of said stripe; means for transferring a corresponding data segment of said plurality of data segments of a next data block of said plurality of data blocks; buffer means for storing XOR parity generated by said means for computing; first means for repeating operation of said means for transferring a corresponding data segment and operation of said means for storing for each data block of said stripe until each corresponding data segment of each block of said plurality of data blocks of said stripe have been transferred; and first means for repeating operation of said means for transferring a first data segment and operation of said means for transferring a corresponding data segment and operation of said means for storing and operation of said means for repeating for a next data segment of said plurality of data segments in each of said plurality of blocks in said data portion of said stripe until all of said plurality of data segments have been transferred.

Claim 11

A DMA controller for use in a RAID storage controller of a RAID storage subsystem, said DMA controller comprising: means for transferring a data portion of a stripe through said DMA controller from a random access source memory to a destination memory, wherein said stripe is stored in a predetermined first order in said source memory and wherein said stripe is transferred to said destination memory in a predetermined second order different from said predetermined first order; and means for computing, within said DMA controller, a plurality of XOR parity segments corresponding to said stripe, wherein said means for computing and said means for transferring are operable substantially simultaneously, wherein said stripe is comprised of a plurality of blocks and wherein each block is comprised of a plurality of segments, and wherein said means for transferring further comprises: means for transferring a first data segment of said plurality of data segments of a data block of said plurality of data blocks of said stripe; means for transferring a corresponding data segment of said plurality of data segments of a next data block of said plurality of data blocks; buffer means for storing XOR parity generated by said means for computing; first means for repeating operation of said means for transferring a corresponding data segment and operation of said means for storing for each data block of said stripe until each corresponding data segment of each block of said plurality of data blocks of said stripe have been transferred; and first means for repeating operation of said means for transferring a first data segment and operation of said means for transferring a corresponding data segment and operation of said means for storing and operation of said means for repeating for a next data segment of said plurality of data segments in each of said plurality of blocks in said data portion of said stripe until all of said plurality of data segments have been transferred.

Claim 12

The DMA controller of claim 8 further comprising: means for storing each of said plurality of XOR parity segments in said destination memory.

Claim 13

The DMA controller of claim 9 wherein said buffer means includes a FIFO for XOR parity accumulation, said FIFO being approximately equal in size to the size of one of said plurality of data segments.

Claim 14

The DMA controller of claim 8 further comprising a storage subsystem including a plurality of disk drives and is operating in a degraded mode having at least one non-functional disk drive with corresponding missing data segments from said plurality of data segments, and wherein said means for transferring includes: means for transferring said plurality of data segments, wherein said means for transfer is devoid of said missing data segments; and means for transferring previously computed associated parity segments, and wherein said means for computing a plurality of XOR parity segments includes: means for computing a plurality of XOR parity segments representative of said missing data segments.

Claim 17

The system of claim 12 wherein said error detection and correction computation element is operable in a plurality of modes and includes: at least one programmable address range register to controllably select an operating mode from said plurality of modes.

Claim 18

The system of claim 13 wherein said buffer includes: a FIFO buffer and where said error detection and correction computation element is controllably operable in a mode wherein data transferred by said DMA transfer controller is stored in said FIFO buffer for purposes of initializing said error detection and correction information.

Claim 19

The system of claim 13 wherein said buffer includes: a FIFO buffer and where said error detection and correction computation element is controllably operable in a mode wherein data transferred by said DMA transfer controller is XOR'd with corresponding error detection and correction information presently stored in said FIFO buffer for purposes of updating said error detection and correction information.

Claim 20

The system of claim 13 wherein said buffer includes: a FIFO buffer and where said error detection and correction computation element is controllably operable in a mode wherein said source memory comprises said FIFO buffer and wherein said data transferred by said DMA transfer controller comprises said error detection and correction information in said FIFO buffer and wherein said error detection and correction information is transferred by said DMA transfer controller to said destination memory.