Fly-by XOR for generating parity for data gleaned from a bus

• US 5,950,225 A
• Filed: 02/28/1997
• Issued: 09/07/1999
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Kleiman, Steven R.
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): Langjahr, David
• Application Number:
  US08/808,396
• Time in Patent Office: 921 Days
• Field of Search: 395/182.04, 711/114, 711/111
• US Class Current: 711/111
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1054 Parity-fast hardware, i.e. dedicated fast hardware for RAID systems with parity

Abstract

The invention provides a method and system for performing XOR operations without consuming substantial computing resources. A specialized processor is coupled to the same bus as a set of disk drives; the specialized processor reviews data transfers to and from the disk drives and performs XOR operations on data transferred to and from the disk drives without requiring separate transfers. The specialized processor maintains an XOR accumulator which is used for XOR operations, which records the result of XOR operations, and which is read out upon command of the processor. The XOR accumulator includes one set of accumulator registers for each RAID stripe, for a selected set of RAID stripes. A memory (such as a contents-addressable memory) associates one set of accumulator registers with each selected RAID stripe.

Claims

1. A method including the steps of

reading at least one block of data from a stripe, said stripe including one storage block on each one of a plurality of mass storage devices, said step of reading including the step of transferring data from said block of data over a bus;

and

while performing said step of transferring said block of data over said bus, accumulating a result of an XOR operation without interfering with said step of transferring.

2. A method as in claim 1, wherein

said step of reading includes copying said block of data to a memory coupled to a processor using a memory bus;

said step of transferring data from said block of data includes the step of transferring data over a secondary bus other than said memory bus; and

said step of accumulating is responsive to said step of transferring said block of data over said secondary bus.

3. A method as in claim 1, wherein

said step of reading includes the step of initiating a DMA transfer from one of said plurality of mass storage devices;

said step of transferring said block of data includes the step of performing said DMA transfer; and

said step of accumulating is responsive to said DMA transfer.

4. A method as in claim 1, wherein

said step of reading includes the step of initiating a DMA transfer from one of said plurality of mass storage devices to a selected memory location;

and

said selected memory location is ignored by said memory, whereby said DMA transfer to said selected memory location to accumulates said result without storing said block of data in said memory.

5. In a system having a processor, a memory, a memory bus coupling said processor and said memory, a plurality of mass storage devices, and a secondary bus coupling said plurality of mass storage devices to said memory bus, a method including the steps of

initiating a DMA operation between at least one of said plurality of mass storage devices and a buffer location in said memory;

monitoring said secondary bus for a plurality of addresses in said buffer location;

copying data associated with said plurality of addresses into an XOR buffer without interfering with said DMA operation; and

accumulating a result of an XOR operation for said data.

6. A method as in claim 5, wherein

said buffer location is ignored by said memory, whereby said DMA operation to said buffer location to accumulates said result without storing said data in said memory.

7. A system including

a processor, a memory bus coupled to said processor, and a memory coupled to said memory bus;

a plurality of mass storage devices and a secondary bus coupling said plurality of mass storage devices to said memory bus, whereby said secondary bus is used for transferring data to and from one of said plurality of mass storage devices; and

an element coupled to said secondary bus, said element including a means for copying data transferred to and from one of said plurality of mass storage devices without interfering with said operation of transferring, and including a means for accumulating a result of an XOR operation for said data.

8. A system as in claim 7, wherein said means for copying includes

a plurality of XOR accumulator buffers;

a first device memory used for matching a portion of a selected memory address with one of said plurality of XOR accumulator buffers;

an XOR operator coupled to said device memory and to said secondary bus, and used for performing an XOR operation on data in a second device memory and data associated with said selected memory address, and for writing a result of said XOR operation into said second device memory.

9. A system as in claim 7, including a DMA transfer element coupled to one of said plurality of mass storage devices;

wherein said DMA transfer element includes a means for recognizing DMA transfers performed by said DMA transfer element, means for copying data from said DMA transfers; and

wherein said means for accumulating is responsive to said means for recognizing and said DMA transfers.

10. A system as in claim 7, including a DMA transfer element coupled to one of said plurality of mass storage devices and used for performing a DMA transfer from said one of said plurality of mass storage devices and a selected memory location;

wherein said selected memory location is ignored by said memory, whereby said DMA transfer to said selected memory location is effective to accumulate said result without storing data in said memory.

11. In a system having a processor, a memory, a memory bus coupling said processor and said memory, a plurality of mass storage devices, and a secondary bus coupling said plurality of mass storage devices to said memory bus, a data structure including

a plurality of XOR accumulator buffers, each having a result of an XOR operation performed on data;

and

a table having a plurality of entries, each entry associating a portion of a memory address with one of said plurality of XOR accumulator buffers, said memory address being associated with said data.