Line data Source code
1 : /*
2 : * Copyright (C) 2013 Andrea Mazzoleni
3 : *
4 : * This program is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 2 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * This program is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : */
14 :
15 : #include "internal.h"
16 : #include "gf.h"
17 :
18 : /*
19 : * Cauchy Matrix Construction for MDS RAID with Arbitrary Parity Levels in GF(2^8)
20 : *
21 : * This is a RAID implementation operating in the Galois Field GF(2^8) with
22 : * the primitive polynomial x^8 + x^4 + x^3 + x^2 + 1 (285 decimal), supporting
23 : * up to six parity levels.
24 : *
25 : * For RAID5 and RAID6, it follows the method described in H. Peter Anvin's
26 : * paper "The mathematics of RAID-6" [1]. Please refer to this paper for a
27 : * complete explanation.
28 : *
29 : * Triple parity was first evaluated using an extension of the same approach,
30 : * with additional parity coefficients set as powers of 2^-1, defined as:
31 : *
32 : * P = sum(Di)
33 : * Q = sum(2^i * Di)
34 : * R = sum(2^-i * Di) for 0 <= i < N
35 : *
36 : * This approach works efficiently for triple parity because multiplications
37 : * and divisions by 2 in GF(2^8) are very fast. It is similar to ZFS RAIDZ3,
38 : * which uses powers of 4 instead of 2^-1.
39 : *
40 : * Unfortunately, this method does not extend beyond triple parity because
41 : * no choice of power coefficients guarantees solvable equations for all
42 : * combinations of missing disks. This is expected: a Vandermonde matrix,
43 : * used in this method, does not ensure that all submatrices are nonsingular
44 : * [2, Chap. 11, Problem 7], which is required for an MDS (Maximum Distance
45 : * Separable) code [2, Chap. 11, Theorem 8].
46 : *
47 : * To overcome this limitation, a Cauchy matrix [3][4] is used for parity
48 : * computation. A Cauchy matrix ensures that all square submatrices are
49 : * nonsingular, so the linear system is always solvable for any combination
50 : * of missing disks. This guarantees an MDS code.
51 : *
52 : * How the matrix is obtained:
53 : *
54 : * The matrix is constructed to match Linux RAID coefficients for the
55 : * first two rows, while ensuring that all square submatrices are nonsingular.
56 : *
57 : * 1. Start by forming a Cauchy matrix with elements defined as 1/(x_i + y_j),
58 : * where all x_i and y_j are distinct elements (the textbook definition
59 : * of a Cauchy matrix).
60 : *
61 : * 2. For the first row (j=0), set x_i = 2^-i and y_0 = 0, resulting in:
62 : *
63 : * row j=0 -> 1/(x_i + y_0) = 1/(2^-i + 0) = 2^i
64 : *
65 : * which reproduces the RAID-6 coefficients.
66 : *
67 : * 3. For subsequent rows (j>0), set y_j = 2^j, yielding:
68 : *
69 : * rows j>0 -> 1/(x_i + y_j) = 1/(2^-i + 2^j)
70 : *
71 : * ensuring x_i != y_j for any i >= 0, j >= 1, and i + j < 255.
72 : *
73 : * 4. Place a row filled with 1 at the top of the matrix, transforming it
74 : * into an Extended Cauchy Matrix. This preserves the nonsingularity
75 : * of all square submatrices.
76 : *
77 : * This first row reproduces the RAID-5 coefficients.
78 : *
79 : * 5. Adjust each row with a factor so that the first column contains all 1s.
80 : * This transformation also preserves the nonsingularity property,
81 : * maintaining the MDS code property.
82 : *
83 : * Concrete example in GF(256) for k=6, m=4:
84 : *
85 : * First, create a 3x6 Cauchy matrix using x_i = 2^-i and y_0 = 0, y_j = 2^j for j>0:
86 : *
87 : * x = { 1, 142, 71, 173, 216, 108 }
88 : * y = { 0, 2, 4 }
89 : *
90 : * The Cauchy matrix is:
91 : *
92 : * 1 2 4 8 16 32
93 : * 244 83 78 183 118 47
94 : * 167 39 213 59 153 82
95 : *
96 : * Divide row 2 by 244 and row 3 by 167. Then extend it with a row of ones
97 : * on top, and it remains MDS. This forms the code for m=4, with RAID-6 as
98 : * a subset:
99 : *
100 : * 1 1 1 1 1 1
101 : * 1 2 4 8 16 32
102 : * 1 245 210 196 154 113
103 : * 1 187 166 215 199 7
104 : *
105 : * Extending the same computation to k=251 and m=6 gives:
106 : *
107 : * This results in the matrix A[row, col] defined as:
108 : *
109 : * 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01...
110 : * 01 02 04 08 10 20 40 80 1d 3a 74 e8 cd 87 13 26 4c 98 2d 5a b4 75...
111 : * 01 f5 d2 c4 9a 71 f1 7f fc 87 c1 c6 19 2f 40 55 3d ba 53 04 9c 61...
112 : * 01 bb a6 d7 c7 07 ce 82 4a 2f a5 9b b6 60 f1 ad e7 f4 06 d2 df 2e...
113 : * 01 97 7f 9c 7c 18 bd a2 58 1a da 74 70 a3 e5 47 29 07 f5 80 23 e9...
114 : * 01 2b 3f cf 73 2c d6 ed cb 74 15 78 8a c1 17 c9 89 68 21 ab 76 3b...
115 : *
116 : * This matrix supports six levels of parity, one for each row, for up to 251
117 : * data disks, one for each column. All the 377,342,351,231 square submatrices
118 : * are nonsingular, verified also by brute-force testing.
119 : *
120 : * This matrix can be extended to support any number of parities by simply
121 : * adding additional rows and removing one column for each new row to maintain
122 : * the condition i + j < 255.
123 : * (See mktables.c for more details on how the matrix is generated.)
124 : *
125 : * The downside is that generic multiplications are required to compute the
126 : * parity, not only fast multiplications by 2^n or 2^-n, which negatively
127 : * affect performance. However, optimized parallel multiplications using SSSE3
128 : * or AVX2 instructions [1][5] make this approach competitive with the triple
129 : * parity computation using power coefficients.
130 : *
131 : * Another advantage of the Cauchy matrix is that the first two rows can
132 : * replicate the RAID5 and RAID6 approach, resulting in a compatible extension.
133 : * SSSE3 or AVX2 instructions are only needed for triple parity or beyond.
134 : *
135 : * Parity computation is as follows:
136 : *
137 : * P = sum(Di)
138 : * Q = sum(2^i * Di)
139 : * R = sum(A[2,i] * Di)
140 : * S = sum(A[3,i] * Di)
141 : * T = sum(A[4,i] * Di)
142 : * U = sum(A[5,i] * Di) for 0 <= i < N
143 : *
144 : * Recovery from six disk failures at indices x, y, z, h, v, w (0 <= x < y < z < h < v < w < N)
145 : * involves computing parity of the remaining N-6 disks:
146 : *
147 : * Pa = sum(Di)
148 : * Qa = sum(2^i * Di)
149 : * Ra = sum(A[2,i] * Di)
150 : * Sa = sum(A[3,i] * Di)
151 : * Ta = sum(A[4,i] * Di)
152 : * Ua = sum(A[5,i] * Di) for i != x,y,z,h,v,w
153 : *
154 : * Defining:
155 : *
156 : * Pd = Pa + P
157 : * Qd = Qa + Q
158 : * Rd = Ra + R
159 : * Sd = Sa + S
160 : * Td = Ta + T
161 : * Ud = Ua + U
162 : *
163 : * yields:
164 : *
165 : * Pd = Dx + Dy + Dz + Dh + Dv + Dw
166 : * Qd = 2^x * Dx + 2^y * Dy + 2^z * Dz + 2^h * Dh + 2^v * Dv + 2^w * Dw
167 : * Rd = A[2,x] * Dx + A[2,y] * Dy + A[2,z] * Dz + A[2,h] * Dh + A[2,v] * Dv + A[2,w] * Dw
168 : * Sd = A[3,x] * Dx + A[3,y] * Dy + A[3,z] * Dz + A[3,h] * Dh + A[3,v] * Dv + A[3,w] * Dw
169 : * Td = A[4,x] * Dx + A[4,y] * Dy + A[4,z] * Dz + A[4,h] * Dh + A[4,v] * Dv + A[4,w] * Dw
170 : * Ud = A[5,x] * Dx + A[5,y] * Dy + A[5,z] * Dz + A[5,h] * Dh + A[5,v] * Dv + A[5,w] * Dw
171 : *
172 : * This linear system is always solvable since the coefficient matrix is
173 : * nonsingular due to the properties of A[].
174 : *
175 : * Example performance on a Intel Core i7-10700 CPU @ 2.90GHz, stripe 256 KiB, 8 data disks:
176 : *
177 : * int8 int32 int64 sse2 sse2e ssse3 ssse3e avx2 avx2e
178 : * gen1 24995 46562 62683 77069
179 : * gen2 8243 15879 25788 27292 44907
180 : * genz 5509 10588 14485 13920 25175
181 : * gen3 1190 13201 14307 27268
182 : * gen4 914 10061 11006 21328
183 : * gen5 746 7970 8828 17040
184 : * gen6 630 6627 7516 14584
185 : *
186 : * Values are in MiB/s of data processed by a single thread.
187 : * Results can be reproduced using "raid/test/speedtest.c".
188 : *
189 : * Triple parity with power coefficients "1, 2, 2^-1" is slightly faster than
190 : * the Cauchy matrix computation if SSSE3 or AVX2 are available:
191 : *
192 : * int8 int32 int64 sse2 ssse3 avx2
193 : * genz 2337 2874 10920 18944
194 : *
195 : * In conclusion, the use of power coefficients, specifically powers
196 : * of 1, 2, and 2^-1, is the best option to implement triple parity on CPUs
197 : * without SSSE3 and AVX2.
198 : * On modern CPUs with SSSE3 or AVX2, the Cauchy matrix is the best
199 : * option because it provides a fast and general approach that works for any
200 : * number of parities.
201 : *
202 : * References:
203 : * [1] Anvin, "The mathematics of RAID-6", 2004
204 : * [2] MacWilliams, Sloane, "The Theory of Error-Correcting Codes", 1977
205 : * [3] Blomer, "An XOR-Based Erasure-Resilient Coding Scheme", 1995
206 : * [4] Roth, "Introduction to Coding Theory", 2006
207 : * [5] Plank, "Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions", 2013
208 : */
209 :
210 : /**
211 : * Generator matrix currently used.
212 : */
213 : const uint8_t (*raid_gfgen)[256];
214 :
215 545 : void raid_mode(int mode)
216 : {
217 545 : if (mode == RAID_MODE_VANDERMONDE) {
218 2 : raid_gen_ptr[2] = raid_genz_ptr;
219 2 : raid_gfgen = gfvandermonde;
220 : } else {
221 543 : raid_gen_ptr[2] = raid_gen3_ptr;
222 543 : raid_gfgen = gfcauchy;
223 : }
224 545 : }
225 :
226 : /**
227 : * Buffer filled with 0 used in recovering.
228 : */
229 : static void *raid_zero_block;
230 :
231 208 : void raid_zero(void *zero)
232 : {
233 208 : raid_zero_block = zero;
234 208 : }
235 :
236 : /*
237 : * Forwarders for parity computation.
238 : *
239 : * These functions compute the parity blocks from the provided data.
240 : *
241 : * The number of parities to compute is implicit in the position in the
242 : * forwarder vector. Position at index #i, computes (#i+1) parities.
243 : *
244 : * All these functions give the guarantee that parities are written
245 : * in order. First parity P, then parity Q, and so on.
246 : * This allows to specify the same memory buffer for multiple parities
247 : * knowing that you'll get the latest written one.
248 : * This characteristic is used by the raid_delta_gen() function to
249 : * avoid to damage unused parities in recovering.
250 : *
251 : * @nd Number of data blocks
252 : * @size Size of the blocks pointed by @v. It must be a multiplier of 64.
253 : * @v Vector of pointers to the blocks of data and parity.
254 : * It has (@nd + #parities) elements. The starting elements are the blocks
255 : * for data, following with the parity blocks.
256 : * Each block has @size bytes.
257 : */
258 : void (*raid_gen_ptr[RAID_PARITY_MAX])(int nd, size_t size, void **vv);
259 : void (*raid_gen3_ptr)(int nd, size_t size, void **vv);
260 : void (*raid_genz_ptr)(int nd, size_t size, void **vv);
261 :
262 1230270 : void raid_gen(int nd, int np, size_t size, void **v)
263 : {
264 : /* enforce limit on size */
265 1230270 : BUG_ON(size % 64 != 0);
266 :
267 : /* enforce limit on number of failures */
268 1230270 : BUG_ON(np < 1);
269 1230270 : BUG_ON(np > RAID_PARITY_MAX);
270 :
271 1230270 : raid_gen_ptr[np - 1](nd, size, v);
272 1230270 : }
273 :
274 : /**
275 : * Inverts the square matrix M of size nxn into V.
276 : *
277 : * This is not a general matrix inversion because we assume the matrix M
278 : * to have all the square submatrix not singular.
279 : * We use Gauss elimination to invert.
280 : *
281 : * @M Matrix to invert with @n rows and @n columns.
282 : * @V Destination matrix where the result is put.
283 : * @n Number of rows and columns of the matrix.
284 : */
285 172567 : void raid_invert(uint8_t *M, uint8_t *V, int n)
286 : {
287 : int i, j, k;
288 :
289 : /* set the identity matrix in V */
290 797758 : for (i = 0; i < n; ++i)
291 3219800 : for (j = 0; j < n; ++j)
292 2594609 : V[i * n + j] = i == j;
293 :
294 : /* for each element in the diagonal */
295 797758 : for (k = 0; k < n; ++k) {
296 : uint8_t f;
297 :
298 : /* the diagonal element cannot be 0 because */
299 : /* we are inverting matrices with all the square */
300 : /* submatrices not singular */
301 625191 : BUG_ON(M[k * n + k] == 0);
302 :
303 : /* make the diagonal element to be 1 */
304 625191 : f = inv(M[k * n + k]);
305 3219800 : for (j = 0; j < n; ++j) {
306 2594609 : M[k * n + j] = mul(f, M[k * n + j]);
307 5189218 : V[k * n + j] = mul(f, V[k * n + j]);
308 : }
309 :
310 : /* make all the elements over and under the diagonal */
311 : /* to be zero */
312 3219800 : for (i = 0; i < n; ++i) {
313 2594609 : if (i == k)
314 625191 : continue;
315 1969418 : f = M[i * n + k];
316 11271318 : for (j = 0; j < n; ++j) {
317 9301900 : M[i * n + j] ^= mul(f, M[k * n + j]);
318 18603800 : V[i * n + j] ^= mul(f, V[k * n + j]);
319 : }
320 : }
321 : }
322 172567 : }
323 :
324 : /**
325 : * Computes the parity without the missing data blocks
326 : * and store it in the buffers of such data blocks.
327 : *
328 : * This is the parity expressed as Pa,Qa,Ra,Sa,Ta,Ua in the equations.
329 : */
330 171553 : void raid_delta_gen(int nr, int *id, int *ip, int nd, size_t size, void **v)
331 : {
332 : void *p[RAID_PARITY_MAX];
333 : void *pa[RAID_PARITY_MAX];
334 : int i, j;
335 : int np;
336 : void *latest;
337 :
338 : /* total number of parities we are going to process */
339 : /* they are both the used and the unused ones */
340 171553 : np = ip[nr - 1] + 1;
341 :
342 : /* latest missing data block */
343 171553 : latest = v[id[nr - 1]];
344 :
345 : /* setup pointers for delta computation */
346 873179 : for (i = 0, j = 0; i < np; ++i) {
347 : /* keep a copy of the original parity vector */
348 701626 : p[i] = v[nd + i];
349 :
350 701626 : if (ip[j] == i) {
351 : /*
352 : * Set used parities to point to the missing
353 : * data blocks.
354 : *
355 : * The related data blocks are instead set
356 : * to point to the "zero" buffer.
357 : */
358 :
359 : /* the latest parity to use ends the for loop and */
360 : /* then it cannot happen to process more of them */
361 605503 : BUG_ON(j >= nr);
362 :
363 : /* buffer for missing data blocks */
364 605503 : pa[j] = v[id[j]];
365 :
366 : /* set at zero the missing data blocks */
367 605503 : v[id[j]] = raid_zero_block;
368 :
369 : /* compute the parity over the missing data blocks */
370 605503 : v[nd + i] = pa[j];
371 :
372 : /* check for the next used entry */
373 605503 : ++j;
374 : } else {
375 : /*
376 : * Unused parities are going to be rewritten with
377 : * not significative data, because we don't have
378 : * functions able to compute only a subset of
379 : * parities.
380 : *
381 : * To avoid this, we reuse parity buffers,
382 : * assuming that all the parity functions write
383 : * parities in order.
384 : *
385 : * We assign the unused parity block to the same
386 : * block of the latest used parity that we know it
387 : * will be written.
388 : *
389 : * This means that this block will be written
390 : * multiple times and only the latest write will
391 : * contain the correct data.
392 : */
393 96123 : v[nd + i] = latest;
394 : }
395 : }
396 :
397 : /* all the parities have to be processed */
398 171553 : BUG_ON(j != nr);
399 :
400 : /* recompute the parity, note that np may be smaller than the */
401 : /* total number of parities available */
402 171553 : raid_gen(nd, np, size, v);
403 :
404 : /* restore data buffers as before */
405 777056 : for (j = 0; j < nr; ++j)
406 605503 : v[id[j]] = pa[j];
407 :
408 : /* restore parity buffers as before */
409 873179 : for (i = 0; i < np; ++i)
410 701626 : v[nd + i] = p[i];
411 171553 : }
412 :
413 : /**
414 : * Recover failure of one data block for PAR1.
415 : *
416 : * Starting from the equation:
417 : *
418 : * Pd = Dx
419 : *
420 : * and solving we get:
421 : *
422 : * Dx = Pd
423 : */
424 96775 : void raid_rec1of1(int *id, int nd, size_t size, void **v)
425 : {
426 : void *p;
427 : void *pa;
428 :
429 : /* for PAR1 we can directly compute the missing block */
430 : /* and we don't need to use the zero buffer */
431 96775 : p = v[nd];
432 96775 : pa = v[id[0]];
433 :
434 : /* use the parity as missing data block */
435 96775 : v[id[0]] = p;
436 :
437 : /* compute the parity over the missing data block */
438 96775 : v[nd] = pa;
439 :
440 : /* compute */
441 96775 : raid_gen(nd, 1, size, v);
442 :
443 : /* restore as before */
444 96775 : v[id[0]] = pa;
445 96775 : v[nd] = p;
446 96775 : }
447 :
448 : /**
449 : * Recover failure of two data blocks for PAR2.
450 : *
451 : * Starting from the equations:
452 : *
453 : * Pd = Dx + Dy
454 : * Qd = 2^id[0] * Dx + 2^id[1] * Dy
455 : *
456 : * and solving we get:
457 : *
458 : * 1 2^(-id[0])
459 : * Dy = ------------------- * Pd + ------------------- * Qd
460 : * 2^(id[1]-id[0]) + 1 2^(id[1]-id[0]) + 1
461 : *
462 : * Dx = Dy + Pd
463 : *
464 : * with conditions:
465 : *
466 : * 2^id[0] != 0
467 : * 2^(id[1]-id[0]) + 1 != 0
468 : *
469 : * That are always satisfied for any 0<=id[0]<id[1]<255.
470 : */
471 132 : void raid_rec2of2_int8(int *id, int *ip, int nd, size_t size, void **vv)
472 : {
473 132 : uint8_t **v = (uint8_t **)vv;
474 : size_t i;
475 : uint8_t *p;
476 : uint8_t *pa;
477 : uint8_t *q;
478 : uint8_t *qa;
479 : const uint8_t *T[2];
480 :
481 : /* get multiplication tables */
482 396 : T[0] = table(inv(pow2(id[1] - id[0]) ^ 1));
483 528 : T[1] = table(inv(pow2(id[0]) ^ pow2(id[1])));
484 :
485 : /* compute delta parity */
486 132 : raid_delta_gen(2, id, ip, nd, size, vv);
487 :
488 132 : p = v[nd];
489 132 : q = v[nd + 1];
490 132 : pa = v[id[0]];
491 132 : qa = v[id[1]];
492 :
493 33924 : for (i = 0; i < size; ++i) {
494 : /* delta */
495 33792 : uint8_t Pd = p[i] ^ pa[i];
496 33792 : uint8_t Qd = q[i] ^ qa[i];
497 :
498 : /* reconstruct */
499 33792 : uint8_t Dy = T[0][Pd] ^ T[1][Qd];
500 33792 : uint8_t Dx = Pd ^ Dy;
501 :
502 : /* set */
503 33792 : pa[i] = Dx;
504 33792 : qa[i] = Dy;
505 : }
506 132 : }
507 :
508 : /*
509 : * Forwarders for data recovery.
510 : *
511 : * These functions recover data blocks using the specified parity
512 : * to recompute the missing data.
513 : *
514 : * Note that the format of vectors @id/@ip is different than raid_rec().
515 : * For example, in the vector @ip the first parity is represented with the
516 : * value 0 and not @nd.
517 : *
518 : * @nr Number of failed data blocks to recover.
519 : * @id[] Vector of @nr indexes of the data blocks to recover.
520 : * The indexes start from 0. They must be in order.
521 : * @ip[] Vector of @nr indexes of the parity blocks to use in the recovering.
522 : * The indexes start from 0. They must be in order.
523 : * @nd Number of data blocks.
524 : * @np Number of parity blocks.
525 : * @size Size of the blocks pointed by @v. It must be a multiplier of 64.
526 : * @v Vector of pointers to the blocks of data and parity.
527 : * It has (@nd + @np) elements. The starting elements are the blocks
528 : * for data, following with the parity blocks.
529 : * Each block has @size bytes.
530 : */
531 : void (*raid_rec_ptr[RAID_PARITY_MAX])(
532 : int nr, int *id, int *ip, int nd, size_t size, void **vv);
533 :
534 870 : void raid_rec(int nr, int *ir, int nd, int np, size_t size, void **v)
535 : {
536 : int nrd; /* number of data blocks to recover */
537 : int nrp; /* number of parity blocks to recover */
538 :
539 : /* enforce limit on size */
540 870 : BUG_ON(size % 64 != 0);
541 :
542 : /* enforce limit on number of failures */
543 870 : BUG_ON(nr > np);
544 870 : BUG_ON(np > RAID_PARITY_MAX);
545 :
546 : /* enforce order in index vector */
547 870 : BUG_ON(nr >= 2 && ir[0] >= ir[1]);
548 870 : BUG_ON(nr >= 3 && ir[1] >= ir[2]);
549 870 : BUG_ON(nr >= 4 && ir[2] >= ir[3]);
550 870 : BUG_ON(nr >= 5 && ir[3] >= ir[4]);
551 870 : BUG_ON(nr >= 6 && ir[4] >= ir[5]);
552 :
553 : /* enforce limit on index vector */
554 870 : BUG_ON(nr > 0 && ir[nr-1] >= nd + np);
555 :
556 : /* count the number of data blocks to recover */
557 870 : nrd = 0;
558 2613 : while (nrd < nr && ir[nrd] < nd)
559 1743 : ++nrd;
560 :
561 : /* all the remaining are parity */
562 870 : nrp = nr - nrd;
563 :
564 : /* enforce limit on number of failures */
565 870 : BUG_ON(nrd > nd);
566 870 : BUG_ON(nrp > np);
567 :
568 : /* if failed data is present */
569 870 : if (nrd != 0) {
570 : int ip[RAID_PARITY_MAX];
571 : int i, j, k;
572 :
573 : /* setup the vector of parities to use */
574 6041 : for (i = 0, j = 0, k = 0; i < np; ++i) {
575 5173 : if (j < nrp && ir[nrd + j] == nd + i) {
576 : /* this parity has to be recovered */
577 22 : ++j;
578 : } else {
579 : /* this parity is used for recovering */
580 5151 : ip[k] = i;
581 5151 : ++k;
582 : }
583 : }
584 :
585 : /* recover the nrd data blocks specified in ir[], */
586 : /* using the first nrd parity in ip[] for recovering */
587 868 : raid_rec_ptr[nrd - 1](nrd, ir, ip, nd, size, v);
588 : }
589 :
590 : /* recompute all the parities up to the last bad one */
591 870 : if (nrp != 0)
592 12 : raid_gen(nd, ir[nr - 1] - nd + 1, size, v);
593 870 : }
594 :
595 210027 : void raid_data(int nr, int *id, int *ip, int nd, size_t size, void **v)
596 : {
597 : /* enforce limit on size */
598 210027 : BUG_ON(size % 64 != 0);
599 :
600 : /* enforce limit on number of failures */
601 210027 : BUG_ON(nr > nd);
602 210027 : BUG_ON(nr > RAID_PARITY_MAX);
603 :
604 : /* enforce order in index vector for data */
605 210027 : BUG_ON(nr >= 2 && id[0] >= id[1]);
606 210027 : BUG_ON(nr >= 3 && id[1] >= id[2]);
607 210027 : BUG_ON(nr >= 4 && id[2] >= id[3]);
608 210027 : BUG_ON(nr >= 5 && id[3] >= id[4]);
609 210027 : BUG_ON(nr >= 6 && id[4] >= id[5]);
610 :
611 : /* enforce limit on index vector for data */
612 210027 : BUG_ON(nr > 0 && id[nr-1] >= nd);
613 :
614 : /* enforce order in index vector for parity */
615 210027 : BUG_ON(nr >= 2 && ip[0] >= ip[1]);
616 210027 : BUG_ON(nr >= 3 && ip[1] >= ip[2]);
617 210027 : BUG_ON(nr >= 4 && ip[2] >= ip[3]);
618 210027 : BUG_ON(nr >= 5 && ip[3] >= ip[4]);
619 210027 : BUG_ON(nr >= 6 && ip[4] >= ip[5]);
620 :
621 : /* if failed data is present */
622 210027 : if (nr != 0)
623 210025 : raid_rec_ptr[nr - 1](nr, id, ip, nd, size, v);
624 210027 : }
625 :
|
