Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : // Copyright (C) 2013 Andrea Mazzoleni
3 :
4 : #include "internal.h"
5 : #include "gf.h"
6 :
7 : /*
8 : * GEN1 (RAID5 with xor) 32bit C implementation
9 : */
10 98 : void raid_gen1_int32(int nd, size_t size, void **vv)
11 : {
12 98 : uint8_t **v = (uint8_t **)vv;
13 : uint8_t *p;
14 : int d, l;
15 : size_t i;
16 :
17 : uint32_t p0;
18 : uint32_t p1;
19 :
20 98 : l = nd - 1;
21 98 : p = v[nd];
22 :
23 3113154 : for (i = 0; i < size; i += 8) {
24 3113056 : p0 = v_32(v[l][i]);
25 3113056 : p1 = v_32(v[l][i + 4]);
26 24905760 : for (d = l - 1; d >= 0; --d) {
27 21792704 : p0 ^= v_32(v[d][i]);
28 21792704 : p1 ^= v_32(v[d][i + 4]);
29 : }
30 3113056 : v_32(p[i]) = p0;
31 3113056 : v_32(p[i + 4]) = p1;
32 : }
33 98 : }
34 :
35 : /*
36 : * GEN1 (RAID5 with xor) 64bit C implementation
37 : */
38 180 : void raid_gen1_int64(int nd, size_t size, void **vv)
39 : {
40 180 : uint8_t **v = (uint8_t **)vv;
41 : uint8_t *p;
42 : int d, l;
43 : size_t i;
44 :
45 : uint64_t p0;
46 : uint64_t p1;
47 :
48 180 : l = nd - 1;
49 180 : p = v[nd];
50 :
51 2900196 : for (i = 0; i < size; i += 16) {
52 2900016 : p0 = v_64(v[l][i]);
53 2900016 : p1 = v_64(v[l][i + 8]);
54 23200784 : for (d = l - 1; d >= 0; --d) {
55 20300768 : p0 ^= v_64(v[d][i]);
56 20300768 : p1 ^= v_64(v[d][i + 8]);
57 : }
58 2900016 : v_64(p[i]) = p0;
59 2900016 : v_64(p[i + 8]) = p1;
60 : }
61 180 : }
62 :
63 : /*
64 : * GEN2 (RAID6 with powers of 2) 32bit C implementation
65 : */
66 51 : void raid_gen2_int32(int nd, size_t size, void **vv)
67 : {
68 51 : uint8_t **v = (uint8_t **)vv;
69 : uint8_t *p;
70 : uint8_t *q;
71 : int d, l;
72 : size_t i;
73 :
74 : uint32_t d0, q0, p0;
75 : uint32_t d1, q1, p1;
76 :
77 51 : l = nd - 1;
78 51 : p = v[nd];
79 51 : q = v[nd + 1];
80 :
81 1573011 : for (i = 0; i < size; i += 8) {
82 1572960 : q0 = p0 = v_32(v[l][i]);
83 1572960 : q1 = p1 = v_32(v[l][i + 4]);
84 12584992 : for (d = l - 1; d >= 0; --d) {
85 11012032 : d0 = v_32(v[d][i]);
86 11012032 : d1 = v_32(v[d][i + 4]);
87 :
88 11012032 : p0 ^= d0;
89 11012032 : p1 ^= d1;
90 :
91 11012032 : q0 = x2_32(q0);
92 11012032 : q1 = x2_32(q1);
93 :
94 11012032 : q0 ^= d0;
95 11012032 : q1 ^= d1;
96 : }
97 1572960 : v_32(p[i]) = p0;
98 1572960 : v_32(p[i + 4]) = p1;
99 1572960 : v_32(q[i]) = q0;
100 1572960 : v_32(q[i + 4]) = q1;
101 : }
102 51 : }
103 :
104 : /*
105 : * GEN2 (RAID6 with powers of 2) 64bit C implementation
106 : */
107 92 : void raid_gen2_int64(int nd, size_t size, void **vv)
108 : {
109 92 : uint8_t **v = (uint8_t **)vv;
110 : uint8_t *p;
111 : uint8_t *q;
112 : int d, l;
113 : size_t i;
114 :
115 : uint64_t d0, q0, p0;
116 : uint64_t d1, q1, p1;
117 :
118 92 : l = nd - 1;
119 92 : p = v[nd];
120 92 : q = v[nd + 1];
121 :
122 1458316 : for (i = 0; i < size; i += 16) {
123 1458224 : q0 = p0 = v_64(v[l][i]);
124 1458224 : q1 = p1 = v_64(v[l][i + 8]);
125 11666448 : for (d = l - 1; d >= 0; --d) {
126 10208224 : d0 = v_64(v[d][i]);
127 10208224 : d1 = v_64(v[d][i + 8]);
128 :
129 10208224 : p0 ^= d0;
130 10208224 : p1 ^= d1;
131 :
132 10208224 : q0 = x2_64(q0);
133 10208224 : q1 = x2_64(q1);
134 :
135 10208224 : q0 ^= d0;
136 10208224 : q1 ^= d1;
137 : }
138 1458224 : v_64(p[i]) = p0;
139 1458224 : v_64(p[i + 8]) = p1;
140 1458224 : v_64(q[i]) = q0;
141 1458224 : v_64(q[i + 8]) = q1;
142 : }
143 92 : }
144 :
145 : /*
146 : * GEN3 (triple parity with Cauchy matrix) 8bit C implementation
147 : *
148 : * Note that instead of a generic multiplication table, likely resulting
149 : * in multiple cache misses, a precomputed table could be used.
150 : * But this is only a kind of reference function, and we are not really
151 : * interested in speed.
152 : */
153 20 : void raid_gen3_int8(int nd, size_t size, void **vv)
154 : {
155 20 : uint8_t **v = (uint8_t **)vv;
156 : uint8_t *p;
157 : uint8_t *q;
158 : uint8_t *r;
159 : int d, l;
160 : size_t i;
161 :
162 : uint8_t d0, r0, q0, p0;
163 :
164 20 : l = nd - 1;
165 20 : p = v[nd];
166 20 : q = v[nd + 1];
167 20 : r = v[nd + 2];
168 :
169 4719124 : for (i = 0; i < size; i += 1) {
170 4719104 : p0 = q0 = r0 = 0;
171 37757184 : for (d = l; d > 0; --d) {
172 33038080 : d0 = v_8(v[d][i]);
173 :
174 33038080 : p0 ^= d0;
175 33038080 : q0 ^= gfmul[d0][gfgen[1][d]];
176 33038080 : r0 ^= gfmul[d0][gfgen[2][d]];
177 : }
178 :
179 : /* first disk with all coefficients at 1 */
180 4719104 : d0 = v_8(v[0][i]);
181 :
182 4719104 : p0 ^= d0;
183 4719104 : q0 ^= d0;
184 4719104 : r0 ^= d0;
185 :
186 4719104 : v_8(p[i]) = p0;
187 4719104 : v_8(q[i]) = q0;
188 4719104 : v_8(r[i]) = r0;
189 : }
190 20 : }
191 :
192 : /*
193 : * GEN4 (quad parity with Cauchy matrix) 8bit C implementation
194 : *
195 : * Note that instead of a generic multiplication table, likely resulting
196 : * in multiple cache misses, a precomputed table could be used.
197 : * But this is only a kind of reference function, and we are not really
198 : * interested in speed.
199 : */
200 17 : void raid_gen4_int8(int nd, size_t size, void **vv)
201 : {
202 17 : uint8_t **v = (uint8_t **)vv;
203 : uint8_t *p;
204 : uint8_t *q;
205 : uint8_t *r;
206 : uint8_t *s;
207 : int d, l;
208 : size_t i;
209 :
210 : uint8_t d0, s0, r0, q0, p0;
211 :
212 17 : l = nd - 1;
213 17 : p = v[nd];
214 17 : q = v[nd + 1];
215 17 : r = v[nd + 2];
216 17 : s = v[nd + 3];
217 :
218 3932689 : for (i = 0; i < size; i += 1) {
219 3932672 : p0 = q0 = r0 = s0 = 0;
220 31465728 : for (d = l; d > 0; --d) {
221 27533056 : d0 = v_8(v[d][i]);
222 :
223 27533056 : p0 ^= d0;
224 27533056 : q0 ^= gfmul[d0][gfgen[1][d]];
225 27533056 : r0 ^= gfmul[d0][gfgen[2][d]];
226 27533056 : s0 ^= gfmul[d0][gfgen[3][d]];
227 : }
228 :
229 : /* first disk with all coefficients at 1 */
230 3932672 : d0 = v_8(v[0][i]);
231 :
232 3932672 : p0 ^= d0;
233 3932672 : q0 ^= d0;
234 3932672 : r0 ^= d0;
235 3932672 : s0 ^= d0;
236 :
237 3932672 : v_8(p[i]) = p0;
238 3932672 : v_8(q[i]) = q0;
239 3932672 : v_8(r[i]) = r0;
240 3932672 : v_8(s[i]) = s0;
241 : }
242 17 : }
243 :
244 : /*
245 : * GEN5 (penta parity with Cauchy matrix) 8bit C implementation
246 : *
247 : * Note that instead of a generic multiplication table, likely resulting
248 : * in multiple cache misses, a precomputed table could be used.
249 : * But this is only a kind of reference function, and we are not really
250 : * interested in speed.
251 : */
252 17 : void raid_gen5_int8(int nd, size_t size, void **vv)
253 : {
254 17 : uint8_t **v = (uint8_t **)vv;
255 : uint8_t *p;
256 : uint8_t *q;
257 : uint8_t *r;
258 : uint8_t *s;
259 : uint8_t *t;
260 : int d, l;
261 : size_t i;
262 :
263 : uint8_t d0, t0, s0, r0, q0, p0;
264 :
265 17 : l = nd - 1;
266 17 : p = v[nd];
267 17 : q = v[nd + 1];
268 17 : r = v[nd + 2];
269 17 : s = v[nd + 3];
270 17 : t = v[nd + 4];
271 :
272 3932689 : for (i = 0; i < size; i += 1) {
273 3932672 : p0 = q0 = r0 = s0 = t0 = 0;
274 31465728 : for (d = l; d > 0; --d) {
275 27533056 : d0 = v_8(v[d][i]);
276 :
277 27533056 : p0 ^= d0;
278 27533056 : q0 ^= gfmul[d0][gfgen[1][d]];
279 27533056 : r0 ^= gfmul[d0][gfgen[2][d]];
280 27533056 : s0 ^= gfmul[d0][gfgen[3][d]];
281 27533056 : t0 ^= gfmul[d0][gfgen[4][d]];
282 : }
283 :
284 : /* first disk with all coefficients at 1 */
285 3932672 : d0 = v_8(v[0][i]);
286 :
287 3932672 : p0 ^= d0;
288 3932672 : q0 ^= d0;
289 3932672 : r0 ^= d0;
290 3932672 : s0 ^= d0;
291 3932672 : t0 ^= d0;
292 :
293 3932672 : v_8(p[i]) = p0;
294 3932672 : v_8(q[i]) = q0;
295 3932672 : v_8(r[i]) = r0;
296 3932672 : v_8(s[i]) = s0;
297 3932672 : v_8(t[i]) = t0;
298 : }
299 17 : }
300 :
301 : /*
302 : * GEN6 (hexa parity with Cauchy matrix) 8bit C implementation
303 : *
304 : * Note that instead of a generic multiplication table, likely resulting
305 : * in multiple cache misses, a precomputed table could be used.
306 : * But this is only a kind of reference function, and we are not really
307 : * interested in speed.
308 : */
309 17 : void raid_gen6_int8(int nd, size_t size, void **vv)
310 : {
311 17 : uint8_t **v = (uint8_t **)vv;
312 : uint8_t *p;
313 : uint8_t *q;
314 : uint8_t *r;
315 : uint8_t *s;
316 : uint8_t *t;
317 : uint8_t *u;
318 : int d, l;
319 : size_t i;
320 :
321 : uint8_t d0, u0, t0, s0, r0, q0, p0;
322 :
323 17 : l = nd - 1;
324 17 : p = v[nd];
325 17 : q = v[nd + 1];
326 17 : r = v[nd + 2];
327 17 : s = v[nd + 3];
328 17 : t = v[nd + 4];
329 17 : u = v[nd + 5];
330 :
331 3932689 : for (i = 0; i < size; i += 1) {
332 3932672 : p0 = q0 = r0 = s0 = t0 = u0 = 0;
333 31465728 : for (d = l; d > 0; --d) {
334 27533056 : d0 = v_8(v[d][i]);
335 :
336 27533056 : p0 ^= d0;
337 27533056 : q0 ^= gfmul[d0][gfgen[1][d]];
338 27533056 : r0 ^= gfmul[d0][gfgen[2][d]];
339 27533056 : s0 ^= gfmul[d0][gfgen[3][d]];
340 27533056 : t0 ^= gfmul[d0][gfgen[4][d]];
341 27533056 : u0 ^= gfmul[d0][gfgen[5][d]];
342 : }
343 :
344 : /* first disk with all coefficients at 1 */
345 3932672 : d0 = v_8(v[0][i]);
346 :
347 3932672 : p0 ^= d0;
348 3932672 : q0 ^= d0;
349 3932672 : r0 ^= d0;
350 3932672 : s0 ^= d0;
351 3932672 : t0 ^= d0;
352 3932672 : u0 ^= d0;
353 :
354 3932672 : v_8(p[i]) = p0;
355 3932672 : v_8(q[i]) = q0;
356 3932672 : v_8(r[i]) = r0;
357 3932672 : v_8(s[i]) = s0;
358 3932672 : v_8(t[i]) = t0;
359 3932672 : v_8(u[i]) = u0;
360 : }
361 17 : }
362 :
363 : /*
364 : * Recover failure of one data block at index id[0] using parity at index
365 : * ip[0] for any RAID level.
366 : *
367 : * Starting from the equation:
368 : *
369 : * Pd = A[ip[0],id[0]] * Dx
370 : *
371 : * and solving we get:
372 : *
373 : * Dx = A[ip[0],id[0]]^-1 * Pd
374 : */
375 127 : void raid_rec1_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
376 : {
377 127 : uint8_t **v = (uint8_t **)vv;
378 : uint8_t *p;
379 : uint8_t *pa;
380 : const uint8_t *T;
381 : uint8_t G;
382 : uint8_t V;
383 : size_t i;
384 :
385 : (void)nr; /* unused, it's always 1 */
386 :
387 : /* if it's RAID5, use the faster function */
388 127 : if (ip[0] == 0) {
389 24 : raid_rec1of1(id, nd, size, vv);
390 24 : return;
391 : }
392 :
393 : /* setup the coefficients matrix */
394 103 : G = A(ip[0], id[0]);
395 :
396 : /* invert it to solve the system of linear equations */
397 103 : V = inv(G);
398 :
399 : /* get multiplication tables */
400 103 : T = table(V);
401 :
402 : /* compute delta parity */
403 103 : raid_delta_gen(1, id, ip, nd, size, vv);
404 :
405 103 : p = v[nd + ip[0]];
406 103 : pa = v[id[0]];
407 :
408 5002343 : for (i = 0; i < size; ++i) {
409 : /* delta */
410 5002240 : uint8_t Pd = p[i] ^ pa[i];
411 :
412 : /* reconstruct */
413 5002240 : pa[i] = T[Pd];
414 : }
415 : }
416 :
417 : /*
418 : * Recover failure of two data blocks at indexes id[0],id[1] using parity at
419 : * indexes ip[0],ip[1] for any RAID level.
420 : *
421 : * Starting from the equations:
422 : *
423 : * Pd = A[ip[0],id[0]] * Dx + A[ip[0],id[1]] * Dy
424 : * Qd = A[ip[1],id[0]] * Dx + A[ip[1],id[1]] * Dy
425 : *
426 : * we solve inverting the coefficients matrix.
427 : */
428 1198 : void raid_rec2_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
429 1198 : {
430 1198 : uint8_t **v = (uint8_t **)vv;
431 : uint8_t *p;
432 : uint8_t *pa;
433 : uint8_t *q;
434 : uint8_t *qa;
435 1198 : const int N = 2;
436 1198 : const uint8_t *T[N][N];
437 1198 : uint8_t G[N * N];
438 1198 : uint8_t V[N * N];
439 : size_t i;
440 : int j, k;
441 :
442 : (void)nr; /* unused, it's always 2 */
443 :
444 : /* if it's RAID6, recovering with P and Q uses the faster function */
445 1198 : if (ip[0] == 0 && ip[1] == 1) {
446 132 : raid_rec2of2_int8(id, ip, nd, size, vv);
447 132 : return;
448 : }
449 :
450 : /* setup the coefficients matrix */
451 3198 : for (j = 0; j < N; ++j)
452 6396 : for (k = 0; k < N; ++k)
453 8528 : G[j * N + k] = A(ip[j], id[k]);
454 :
455 : /* invert it to solve the system of linear equations */
456 1066 : raid_invert(G, V, N);
457 :
458 : /* get multiplication tables */
459 3198 : for (j = 0; j < N; ++j)
460 6396 : for (k = 0; k < N; ++k)
461 8528 : T[j][k] = table(V[j * N + k]);
462 :
463 : /* compute delta parity */
464 1066 : raid_delta_gen(2, id, ip, nd, size, vv);
465 :
466 1066 : p = v[nd + ip[0]];
467 1066 : q = v[nd + ip[1]];
468 1066 : pa = v[id[0]];
469 1066 : qa = v[id[1]];
470 :
471 2892842 : for (i = 0; i < size; ++i) {
472 : /* delta */
473 2891776 : uint8_t Pd = p[i] ^ pa[i];
474 2891776 : uint8_t Qd = q[i] ^ qa[i];
475 :
476 : /* reconstruct */
477 2891776 : pa[i] = T[0][0][Pd] ^ T[0][1][Qd];
478 2891776 : qa[i] = T[1][0][Pd] ^ T[1][1][Qd];
479 : }
480 : }
481 :
482 : /*
483 : * Recover failure of N data blocks at indexes id[N] using parity at indexes
484 : * ip[N] for any RAID level.
485 : *
486 : * Starting from the N equations, with 0<=i<N :
487 : *
488 : * PD[i] = sum(A[ip[i],id[j]] * D[i]) 0<=j<N
489 : *
490 : * we solve inverting the coefficients matrix.
491 : *
492 : * Note that referring to previous equations you have:
493 : * PD[0] = Pd, PD[1] = Qd, PD[2] = Rd, ...
494 : * D[0] = Dx, D[1] = Dy, D[2] = Dz, ...
495 : */
496 17741 : void raid_recX_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
497 : {
498 17741 : uint8_t **v = (uint8_t **)vv;
499 : uint8_t *p[RAID_PARITY_MAX];
500 : uint8_t *pa[RAID_PARITY_MAX];
501 : const uint8_t *T[RAID_PARITY_MAX][RAID_PARITY_MAX];
502 : uint8_t G[RAID_PARITY_MAX * RAID_PARITY_MAX];
503 : uint8_t V[RAID_PARITY_MAX * RAID_PARITY_MAX];
504 : size_t i;
505 : int j, k;
506 :
507 : /* setup the coefficients matrix */
508 90695 : for (j = 0; j < nr; ++j)
509 385828 : for (k = 0; k < nr; ++k)
510 625748 : G[j * nr + k] = A(ip[j], id[k]);
511 :
512 : /* invert it to solve the system of linear equations */
513 17741 : raid_invert(G, V, nr);
514 :
515 : /* get multiplication tables */
516 90695 : for (j = 0; j < nr; ++j)
517 385828 : for (k = 0; k < nr; ++k)
518 625748 : T[j][k] = table(V[j * nr + k]);
519 :
520 : /* compute delta parity */
521 17741 : raid_delta_gen(nr, id, ip, nd, size, vv);
522 :
523 90695 : for (j = 0; j < nr; ++j) {
524 72954 : p[j] = v[nd + ip[j]];
525 72954 : pa[j] = v[id[j]];
526 : }
527 :
528 9797197 : for (i = 0; i < size; ++i) {
529 : uint8_t PD[RAID_PARITY_MAX];
530 :
531 : /* delta */
532 52025600 : for (j = 0; j < nr; ++j)
533 42246144 : PD[j] = p[j][i] ^ pa[j][i];
534 :
535 : /* reconstruct */
536 52025600 : for (j = 0; j < nr; ++j) {
537 42246144 : uint8_t b = 0;
538 :
539 234953728 : for (k = 0; k < nr; ++k)
540 192707584 : b ^= T[j][k][PD[k]];
541 42246144 : pa[j][i] = b;
542 : }
543 : }
544 17741 : }
545 :
546 322 : void raid_register_int(void)
547 : {
548 : if (sizeof(void *) == 4) {
549 : raid_gen_register(RAID_ALGO_CAUCHY_PAR1, "int32", raid_gen1_int32);
550 : raid_gen_register(RAID_ALGO_CAUCHY_PAR2, "int32", raid_gen2_int32);
551 : raid_gen_register(RAID_ALGO_VANDERMONDE_PAR3, "int32", raid_genz_int32);
552 : } else {
553 322 : raid_gen_register(RAID_ALGO_CAUCHY_PAR1, "int64", raid_gen1_int64);
554 322 : raid_gen_register(RAID_ALGO_CAUCHY_PAR2, "int64", raid_gen2_int64);
555 322 : raid_gen_register(RAID_ALGO_VANDERMONDE_PAR3, "int64", raid_genz_int64);
556 : }
557 322 : raid_gen_register(RAID_ALGO_CAUCHY_PAR3, "int8", raid_gen3_int8);
558 322 : raid_gen_register(RAID_ALGO_CAUCHY_PAR4, "int8", raid_gen4_int8);
559 322 : raid_gen_register(RAID_ALGO_CAUCHY_PAR5, "int8", raid_gen5_int8);
560 322 : raid_gen_register(RAID_ALGO_CAUCHY_PAR6, "int8", raid_gen6_int8);
561 :
562 322 : raid_rec_register(RAID_ALGO_CAUCHY_PAR1, "int8", raid_rec1_int8);
563 322 : raid_rec_register(RAID_ALGO_CAUCHY_PAR2, "int8", raid_rec2_int8);
564 322 : raid_rec_register(RAID_ALGO_CAUCHY_PAR3, "int8", raid_recX_int8);
565 322 : raid_rec_register(RAID_ALGO_CAUCHY_PAR4, "int8", raid_recX_int8);
566 322 : raid_rec_register(RAID_ALGO_CAUCHY_PAR5, "int8", raid_recX_int8);
567 322 : raid_rec_register(RAID_ALGO_CAUCHY_PAR6, "int8", raid_recX_int8);
568 322 : }
|
