2 * Copyright (C) 2013 Andrea Mazzoleni
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.
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.
19 * GEN1 (RAID5 with xor) 32bit C implementation
21 void raid_gen1_int32(int nd, size_t size, void **vv)
23 uint8_t **v = (uint8_t **)vv;
34 for (i = 0; i < size; i += 8) {
36 p1 = v_32(v[l][i + 4]);
37 for (d = l - 1; d >= 0; --d) {
39 p1 ^= v_32(v[d][i + 4]);
47 * GEN1 (RAID5 with xor) 64bit C implementation
49 void raid_gen1_int64(int nd, size_t size, void **vv)
51 uint8_t **v = (uint8_t **)vv;
62 for (i = 0; i < size; i += 16) {
64 p1 = v_64(v[l][i + 8]);
65 for (d = l - 1; d >= 0; --d) {
67 p1 ^= v_64(v[d][i + 8]);
75 * GEN2 (RAID6 with powers of 2) 32bit C implementation
77 void raid_gen2_int32(int nd, size_t size, void **vv)
79 uint8_t **v = (uint8_t **)vv;
92 for (i = 0; i < size; i += 8) {
93 q0 = p0 = v_32(v[l][i]);
94 q1 = p1 = v_32(v[l][i + 4]);
95 for (d = l - 1; d >= 0; --d) {
97 d1 = v_32(v[d][i + 4]);
116 * GEN2 (RAID6 with powers of 2) 64bit C implementation
118 void raid_gen2_int64(int nd, size_t size, void **vv)
120 uint8_t **v = (uint8_t **)vv;
133 for (i = 0; i < size; i += 16) {
134 q0 = p0 = v_64(v[l][i]);
135 q1 = p1 = v_64(v[l][i + 8]);
136 for (d = l - 1; d >= 0; --d) {
138 d1 = v_64(v[d][i + 8]);
157 * GEN3 (triple parity with Cauchy matrix) 8bit C implementation
159 * Note that instead of a generic multiplication table, likely resulting
160 * in multiple cache misses, a precomputed table could be used.
161 * But this is only a kind of reference function, and we are not really
162 * interested in speed.
164 void raid_gen3_int8(int nd, size_t size, void **vv)
166 uint8_t **v = (uint8_t **)vv;
173 uint8_t d0, r0, q0, p0;
180 for (i = 0; i < size; i += 1) {
182 for (d = l; d > 0; --d) {
186 q0 ^= gfmul[d0][gfgen[1][d]];
187 r0 ^= gfmul[d0][gfgen[2][d]];
190 /* first disk with all coefficients at 1 */
204 * GEN4 (quad parity with Cauchy matrix) 8bit C implementation
206 * Note that instead of a generic multiplication table, likely resulting
207 * in multiple cache misses, a precomputed table could be used.
208 * But this is only a kind of reference function, and we are not really
209 * interested in speed.
211 void raid_gen4_int8(int nd, size_t size, void **vv)
213 uint8_t **v = (uint8_t **)vv;
221 uint8_t d0, s0, r0, q0, p0;
229 for (i = 0; i < size; i += 1) {
230 p0 = q0 = r0 = s0 = 0;
231 for (d = l; d > 0; --d) {
235 q0 ^= gfmul[d0][gfgen[1][d]];
236 r0 ^= gfmul[d0][gfgen[2][d]];
237 s0 ^= gfmul[d0][gfgen[3][d]];
240 /* first disk with all coefficients at 1 */
256 * GEN5 (penta parity with Cauchy matrix) 8bit C implementation
258 * Note that instead of a generic multiplication table, likely resulting
259 * in multiple cache misses, a precomputed table could be used.
260 * But this is only a kind of reference function, and we are not really
261 * interested in speed.
263 void raid_gen5_int8(int nd, size_t size, void **vv)
265 uint8_t **v = (uint8_t **)vv;
274 uint8_t d0, t0, s0, r0, q0, p0;
283 for (i = 0; i < size; i += 1) {
284 p0 = q0 = r0 = s0 = t0 = 0;
285 for (d = l; d > 0; --d) {
289 q0 ^= gfmul[d0][gfgen[1][d]];
290 r0 ^= gfmul[d0][gfgen[2][d]];
291 s0 ^= gfmul[d0][gfgen[3][d]];
292 t0 ^= gfmul[d0][gfgen[4][d]];
295 /* first disk with all coefficients at 1 */
313 * GEN6 (hexa parity with Cauchy matrix) 8bit C implementation
315 * Note that instead of a generic multiplication table, likely resulting
316 * in multiple cache misses, a precomputed table could be used.
317 * But this is only a kind of reference function, and we are not really
318 * interested in speed.
320 void raid_gen6_int8(int nd, size_t size, void **vv)
322 uint8_t **v = (uint8_t **)vv;
332 uint8_t d0, u0, t0, s0, r0, q0, p0;
342 for (i = 0; i < size; i += 1) {
343 p0 = q0 = r0 = s0 = t0 = u0 = 0;
344 for (d = l; d > 0; --d) {
348 q0 ^= gfmul[d0][gfgen[1][d]];
349 r0 ^= gfmul[d0][gfgen[2][d]];
350 s0 ^= gfmul[d0][gfgen[3][d]];
351 t0 ^= gfmul[d0][gfgen[4][d]];
352 u0 ^= gfmul[d0][gfgen[5][d]];
355 /* first disk with all coefficients at 1 */
375 * Recover failure of one data block at index id[0] using parity at index
376 * ip[0] for any RAID level.
378 * Starting from the equation:
380 * Pd = A[ip[0],id[0]] * Dx
382 * and solving we get:
384 * Dx = A[ip[0],id[0]]^-1 * Pd
386 void raid_rec1_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
388 uint8_t **v = (uint8_t **)vv;
396 (void)nr; /* unused, it's always 1 */
398 /* if it's RAID5 uses the faster function */
400 raid_rec1of1(id, nd, size, vv);
404 /* setup the coefficients matrix */
407 /* invert it to solve the system of linear equations */
410 /* get multiplication tables */
413 /* compute delta parity */
414 raid_delta_gen(1, id, ip, nd, size, vv);
419 for (i = 0; i < size; ++i) {
421 uint8_t Pd = p[i] ^ pa[i];
429 * Recover failure of two data blocks at indexes id[0],id[1] using parity at
430 * indexes ip[0],ip[1] for any RAID level.
432 * Starting from the equations:
434 * Pd = A[ip[0],id[0]] * Dx + A[ip[0],id[1]] * Dy
435 * Qd = A[ip[1],id[0]] * Dx + A[ip[1],id[1]] * Dy
437 * we solve inverting the coefficients matrix.
439 void raid_rec2_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
441 uint8_t **v = (uint8_t **)vv;
447 const uint8_t *T[N][N];
453 (void)nr; /* unused, it's always 2 */
455 /* if it's RAID6 recovering with P and Q uses the faster function */
456 if (ip[0] == 0 && ip[1] == 1) {
457 raid_rec2of2_int8(id, ip, nd, size, vv);
461 /* setup the coefficients matrix */
462 for (j = 0; j < N; ++j)
463 for (k = 0; k < N; ++k)
464 G[j * N + k] = A(ip[j], id[k]);
466 /* invert it to solve the system of linear equations */
467 raid_invert(G, V, N);
469 /* get multiplication tables */
470 for (j = 0; j < N; ++j)
471 for (k = 0; k < N; ++k)
472 T[j][k] = table(V[j * N + k]);
474 /* compute delta parity */
475 raid_delta_gen(2, id, ip, nd, size, vv);
482 for (i = 0; i < size; ++i) {
484 uint8_t Pd = p[i] ^ pa[i];
485 uint8_t Qd = q[i] ^ qa[i];
488 pa[i] = T[0][0][Pd] ^ T[0][1][Qd];
489 qa[i] = T[1][0][Pd] ^ T[1][1][Qd];
494 * Recover failure of N data blocks at indexes id[N] using parity at indexes
495 * ip[N] for any RAID level.
497 * Starting from the N equations, with 0<=i<N :
499 * PD[i] = sum(A[ip[i],id[j]] * D[i]) 0<=j<N
501 * we solve inverting the coefficients matrix.
503 * Note that referring at previous equations you have:
504 * PD[0] = Pd, PD[1] = Qd, PD[2] = Rd, ...
505 * D[0] = Dx, D[1] = Dy, D[2] = Dz, ...
507 void raid_recX_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
509 uint8_t **v = (uint8_t **)vv;
510 uint8_t *p[RAID_PARITY_MAX];
511 uint8_t *pa[RAID_PARITY_MAX];
512 const uint8_t *T[RAID_PARITY_MAX][RAID_PARITY_MAX];
513 uint8_t G[RAID_PARITY_MAX * RAID_PARITY_MAX];
514 uint8_t V[RAID_PARITY_MAX * RAID_PARITY_MAX];
518 /* setup the coefficients matrix */
519 for (j = 0; j < nr; ++j)
520 for (k = 0; k < nr; ++k)
521 G[j * nr + k] = A(ip[j], id[k]);
523 /* invert it to solve the system of linear equations */
524 raid_invert(G, V, nr);
526 /* get multiplication tables */
527 for (j = 0; j < nr; ++j)
528 for (k = 0; k < nr; ++k)
529 T[j][k] = table(V[j * nr + k]);
531 /* compute delta parity */
532 raid_delta_gen(nr, id, ip, nd, size, vv);
534 for (j = 0; j < nr; ++j) {
535 p[j] = v[nd + ip[j]];
539 for (i = 0; i < size; ++i) {
540 uint8_t PD[RAID_PARITY_MAX];
543 for (j = 0; j < nr; ++j)
544 PD[j] = p[j][i] ^ pa[j][i];
547 for (j = 0; j < nr; ++j) {
550 for (k = 0; k < nr; ++k)