Efficient parity operations

1. A method of performing parity operations in a redundant data storage system that utilizes a plurality of data segments and at least two corresponding parity segments, wherein the parity segments are derived from the data segments and from parity coefficients corresponding to respective data segments, and wherein there are different parity operations involving different subsets of the parity coefficients, the method comprising the following steps:

pre-selecting parity coefficient subsets for use in the different parity operations;

storing all of the pre-selected parity coefficient subsets in a memory; determining which of the stored subsets of parity coefficients is needed for the particular parity operation;

reading the determined subset of parity coefficients from the memory;

performing the particular parity operation with the subset of parity coefficients that was read from the memory.

2. A method as recited in claim 1 , wherein:

the storing step comprises pre-formatting the pre-selected parity coefficient subsets in an indexed memory array; and

the step of performing the particular parity operation is accomplished by hardware-based parity operation logic that utilizes the subsets of parity coefficients as they are pre-formatted in the memory array.

3. A method as recited in claim 1 , further comprising:

classifying the different parity operations into classifications comprising:

parity segment generation operations;

parity segment regeneration operations;

data segment reconstruction operations;

wherein each classification of parity operations includes a plurality of different classification scenarios, each classification scenario involving a respective set of parity coefficients;

wherein the pre-selecting step comprises pre-selecting parity coefficient subsets for each of the different classification scenarios;

wherein the storing step comprises pre-formatting the pre-selected parity coefficient subsets in an indexed memory array; and

wherein the step of performing the particular parity operation is accomplished by hardware-based parity operation logic that utilizes the subsets of parity coefficients as they are pre-formatted in the indexed memory array.

4. A method as recited in claim 1 , further comprising:

classifying the different parity operations into classifications comprising:

parity segment generation operations;

parity segment regeneration operations;

data segment reconstruction operations;

wherein each classification of parity operations includes a plurality of different classification scenarios, each classification scenario involving a respective subset of parity coefficients;

wherein the pre-selecting step comprises pre-selecting parity coefficient subsets for each of the different classification scenarios;

wherein the storing step comprises grouping the pre-selected parity coefficient subsets in an indexed memory array in accordance with the classifications of the pre-selected parity coefficient subsets.

5. A method as recited in claim 1 , further comprising:

classifying the different parity operations into classifications comprising:

parity segment generation operations;

parity segment regeneration operations;

data segment reconstruction operations;

wherein each classification of parity operations includes a plurality of different classification scenarios, each classification scenario involving a respective subset of parity coefficients, the subsets of parity coefficients having varying subset sizes;

wherein the pre-selecting step comprises pre-selecting parity coefficient subsets for each of the different classification scenarios;

grouping the pre-selected parity coefficient subsets into classification groups;

sub-grouping at least one of the classification groups into sub-groups according to subset size;

wherein the storing step comprises packing the pre-selected parity coefficient subsets in an indexed memory array, segregated by group and sub-group.

6. A method as recited in claim 1 , wherein the different parity operations include parity regeneration operations that include a plurality of different operation scenarios, each operation scenario involving a respective subset of parity coefficients, the respective subsets containing all possible ranges P x through p y , of a base set of N parameter coefficients referred to as P o through P N−1 , the method further comprising:

forming groups of the subsets according to subset size;

packing the groups of subsets in order of increasing subset size in a linear memory array;

calculating an offset in the linear memory array of a particular group i corresponding to a subset size L i in accordance with a predefined function of N and L i ;

reading a subset of values from the particular group corresponding to the subset size of L i at the calculated offset in the linear memory array.

7. A method of accessing pre-selected subsets of values, wherein the respective subsets contain all possible ranges P x through p y of a base set of N values referred to as P o through p N−1 , the method comprising the following steps:

forming groups of the subsets, wherein the groups correspond respectively to different subset sizes;

packing the groups of subsets in order of increasing subset size in a linear memory array;

calculating an offset in the linear memory array of a particular group i corresponding to a subset size L i in accordance with a predefined function of N and L i ;

reading a subset of values from the particular group i at the calculated offset in the linear memory array.

8. A method as recited in claim 7 , wherein group i has N−L i +1 subsets of parity coefficients, and wherein the calculating step is performed by evaluating a formula comprising:

((L i −1)(12N+(L i )(3N−2L i −5))/6)−3(N−1).

9. A method as recited in claim 7 , further comprising:

within any individual group i, calculating a memory offset of a subset D in the individual group as a function of subset size L i .

10. A disk controller that performs parity operations in a redundant data storage system that utilizes a plurality of data segments and at least two corresponding parity segments, wherein the parity segments are derived from the data segments and from parity coefficients corresponding to respective data segments, and wherein there are different parity operations involving different subsets of parity coefficients, comprising:

a memory containing stored subsets of parity coefficients corresponding respectively to different parity-related computation scenarios;

hardware parity computation logic configured to any particular parity-related operation by (a) determining the scenario of the operation, (b) reading the corresponding subset of parity coefficients from the memory, and (c) performing the particular parity-related operation with the subset of parity coefficients read from the memory.

11. A disk controller as recited in claim 10 , wherein the stored subsets are indexed within the memory.

12. A disk controller as recited in claim 10 , wherein:

the parity-related computation scenarios are classified under classifications comprising:

parity segment generation operations;

parity segment regeneration operations;

data segment reconstruction operations;

the stored subsets are grouped in the memory in accordance with the classifications of the corresponding parity-related computation scenarios.

13. A disk controller as recited in claim 10 , wherein:

the parity-related computation scenarios are classified under classifications comprising:

panty segment generation operations;

parity segment regeneration operations;

data segment reconstruction operations;

the stored subsets are grouped in the memory into classification groups, in accordance with the classifications of the corresponding parity-related computation scenarios.