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 : * GEN1 (RAID5 with xor) 32bit C implementation
20 : */
21 129 : void raid_gen1_int32(int nd, size_t size, void **vv)
22 : {
23 129 : uint8_t **v = (uint8_t **)vv;
24 : uint8_t *p;
25 : int d, l;
26 : size_t i;
27 :
28 : uint32_t p0;
29 : uint32_t p1;
30 :
31 129 : l = nd - 1;
32 129 : p = v[nd];
33 :
34 4128993 : for (i = 0; i < size; i += 8) {
35 4128864 : p0 = v_32(v[l][i]);
36 4128864 : p1 = v_32(v[l][i + 4]);
37 33032224 : for (d = l - 1; d >= 0; --d) {
38 28903360 : p0 ^= v_32(v[d][i]);
39 28903360 : p1 ^= v_32(v[d][i + 4]);
40 : }
41 4128864 : v_32(p[i]) = p0;
42 4128864 : v_32(p[i + 4]) = p1;
43 : }
44 129 : }
45 :
46 : /*
47 : * GEN1 (RAID5 with xor) 64bit C implementation
48 : */
49 245 : void raid_gen1_int64(int nd, size_t size, void **vv)
50 : {
51 245 : uint8_t **v = (uint8_t **)vv;
52 : uint8_t *p;
53 : int d, l;
54 : size_t i;
55 :
56 : uint64_t p0;
57 : uint64_t p1;
58 :
59 245 : l = nd - 1;
60 245 : p = v[nd];
61 :
62 3965221 : for (i = 0; i < size; i += 16) {
63 3964976 : p0 = v_64(v[l][i]);
64 3964976 : p1 = v_64(v[l][i + 8]);
65 31720464 : for (d = l - 1; d >= 0; --d) {
66 27755488 : p0 ^= v_64(v[d][i]);
67 27755488 : p1 ^= v_64(v[d][i + 8]);
68 : }
69 3964976 : v_64(p[i]) = p0;
70 3964976 : v_64(p[i + 8]) = p1;
71 : }
72 245 : }
73 :
74 : /*
75 : * GEN2 (RAID6 with powers of 2) 32bit C implementation
76 : */
77 51 : void raid_gen2_int32(int nd, size_t size, void **vv)
78 : {
79 51 : uint8_t **v = (uint8_t **)vv;
80 : uint8_t *p;
81 : uint8_t *q;
82 : int d, l;
83 : size_t i;
84 :
85 : uint32_t d0, q0, p0;
86 : uint32_t d1, q1, p1;
87 :
88 51 : l = nd - 1;
89 51 : p = v[nd];
90 51 : q = v[nd + 1];
91 :
92 1573011 : for (i = 0; i < size; i += 8) {
93 1572960 : q0 = p0 = v_32(v[l][i]);
94 1572960 : q1 = p1 = v_32(v[l][i + 4]);
95 12584992 : for (d = l - 1; d >= 0; --d) {
96 11012032 : d0 = v_32(v[d][i]);
97 11012032 : d1 = v_32(v[d][i + 4]);
98 :
99 11012032 : p0 ^= d0;
100 11012032 : p1 ^= d1;
101 :
102 11012032 : q0 = x2_32(q0);
103 11012032 : q1 = x2_32(q1);
104 :
105 11012032 : q0 ^= d0;
106 11012032 : q1 ^= d1;
107 : }
108 1572960 : v_32(p[i]) = p0;
109 1572960 : v_32(p[i + 4]) = p1;
110 1572960 : v_32(q[i]) = q0;
111 1572960 : v_32(q[i + 4]) = q1;
112 : }
113 51 : }
114 :
115 : /*
116 : * GEN2 (RAID6 with powers of 2) 64bit C implementation
117 : */
118 95 : void raid_gen2_int64(int nd, size_t size, void **vv)
119 : {
120 95 : uint8_t **v = (uint8_t **)vv;
121 : uint8_t *p;
122 : uint8_t *q;
123 : int d, l;
124 : size_t i;
125 :
126 : uint64_t d0, q0, p0;
127 : uint64_t d1, q1, p1;
128 :
129 95 : l = nd - 1;
130 95 : p = v[nd];
131 95 : q = v[nd + 1];
132 :
133 1507471 : for (i = 0; i < size; i += 16) {
134 1507376 : q0 = p0 = v_64(v[l][i]);
135 1507376 : q1 = p1 = v_64(v[l][i + 8]);
136 12059664 : for (d = l - 1; d >= 0; --d) {
137 10552288 : d0 = v_64(v[d][i]);
138 10552288 : d1 = v_64(v[d][i + 8]);
139 :
140 10552288 : p0 ^= d0;
141 10552288 : p1 ^= d1;
142 :
143 10552288 : q0 = x2_64(q0);
144 10552288 : q1 = x2_64(q1);
145 :
146 10552288 : q0 ^= d0;
147 10552288 : q1 ^= d1;
148 : }
149 1507376 : v_64(p[i]) = p0;
150 1507376 : v_64(p[i + 8]) = p1;
151 1507376 : v_64(q[i]) = q0;
152 1507376 : v_64(q[i + 8]) = q1;
153 : }
154 95 : }
155 :
156 : /*
157 : * GEN3 (triple parity with Cauchy matrix) 8bit C implementation
158 : *
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.
163 : */
164 30 : void raid_gen3_int8(int nd, size_t size, void **vv)
165 : {
166 30 : uint8_t **v = (uint8_t **)vv;
167 : uint8_t *p;
168 : uint8_t *q;
169 : uint8_t *r;
170 : int d, l;
171 : size_t i;
172 :
173 : uint8_t d0, r0, q0, p0;
174 :
175 30 : l = nd - 1;
176 30 : p = v[nd];
177 30 : q = v[nd + 1];
178 30 : r = v[nd + 2];
179 :
180 7340574 : for (i = 0; i < size; i += 1) {
181 7340544 : p0 = q0 = r0 = 0;
182 58728704 : for (d = l; d > 0; --d) {
183 51388160 : d0 = v_8(v[d][i]);
184 :
185 51388160 : p0 ^= d0;
186 51388160 : q0 ^= gfmul[d0][gfgen[1][d]];
187 51388160 : r0 ^= gfmul[d0][gfgen[2][d]];
188 : }
189 :
190 : /* first disk with all coefficients at 1 */
191 7340544 : d0 = v_8(v[0][i]);
192 :
193 7340544 : p0 ^= d0;
194 7340544 : q0 ^= d0;
195 7340544 : r0 ^= d0;
196 :
197 7340544 : v_8(p[i]) = p0;
198 7340544 : v_8(q[i]) = q0;
199 7340544 : v_8(r[i]) = r0;
200 : }
201 30 : }
202 :
203 : /*
204 : * GEN4 (quad parity with Cauchy matrix) 8bit C implementation
205 : *
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.
210 : */
211 21 : void raid_gen4_int8(int nd, size_t size, void **vv)
212 : {
213 21 : uint8_t **v = (uint8_t **)vv;
214 : uint8_t *p;
215 : uint8_t *q;
216 : uint8_t *r;
217 : uint8_t *s;
218 : int d, l;
219 : size_t i;
220 :
221 : uint8_t d0, s0, r0, q0, p0;
222 :
223 21 : l = nd - 1;
224 21 : p = v[nd];
225 21 : q = v[nd + 1];
226 21 : r = v[nd + 2];
227 21 : s = v[nd + 3];
228 :
229 4981269 : for (i = 0; i < size; i += 1) {
230 4981248 : p0 = q0 = r0 = s0 = 0;
231 39854336 : for (d = l; d > 0; --d) {
232 34873088 : d0 = v_8(v[d][i]);
233 :
234 34873088 : p0 ^= d0;
235 34873088 : q0 ^= gfmul[d0][gfgen[1][d]];
236 34873088 : r0 ^= gfmul[d0][gfgen[2][d]];
237 34873088 : s0 ^= gfmul[d0][gfgen[3][d]];
238 : }
239 :
240 : /* first disk with all coefficients at 1 */
241 4981248 : d0 = v_8(v[0][i]);
242 :
243 4981248 : p0 ^= d0;
244 4981248 : q0 ^= d0;
245 4981248 : r0 ^= d0;
246 4981248 : s0 ^= d0;
247 :
248 4981248 : v_8(p[i]) = p0;
249 4981248 : v_8(q[i]) = q0;
250 4981248 : v_8(r[i]) = r0;
251 4981248 : v_8(s[i]) = s0;
252 : }
253 21 : }
254 :
255 : /*
256 : * GEN5 (penta parity with Cauchy matrix) 8bit C implementation
257 : *
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.
262 : */
263 18 : void raid_gen5_int8(int nd, size_t size, void **vv)
264 : {
265 18 : uint8_t **v = (uint8_t **)vv;
266 : uint8_t *p;
267 : uint8_t *q;
268 : uint8_t *r;
269 : uint8_t *s;
270 : uint8_t *t;
271 : int d, l;
272 : size_t i;
273 :
274 : uint8_t d0, t0, s0, r0, q0, p0;
275 :
276 18 : l = nd - 1;
277 18 : p = v[nd];
278 18 : q = v[nd + 1];
279 18 : r = v[nd + 2];
280 18 : s = v[nd + 3];
281 18 : t = v[nd + 4];
282 :
283 4194834 : for (i = 0; i < size; i += 1) {
284 4194816 : p0 = q0 = r0 = s0 = t0 = 0;
285 33562880 : for (d = l; d > 0; --d) {
286 29368064 : d0 = v_8(v[d][i]);
287 :
288 29368064 : p0 ^= d0;
289 29368064 : q0 ^= gfmul[d0][gfgen[1][d]];
290 29368064 : r0 ^= gfmul[d0][gfgen[2][d]];
291 29368064 : s0 ^= gfmul[d0][gfgen[3][d]];
292 29368064 : t0 ^= gfmul[d0][gfgen[4][d]];
293 : }
294 :
295 : /* first disk with all coefficients at 1 */
296 4194816 : d0 = v_8(v[0][i]);
297 :
298 4194816 : p0 ^= d0;
299 4194816 : q0 ^= d0;
300 4194816 : r0 ^= d0;
301 4194816 : s0 ^= d0;
302 4194816 : t0 ^= d0;
303 :
304 4194816 : v_8(p[i]) = p0;
305 4194816 : v_8(q[i]) = q0;
306 4194816 : v_8(r[i]) = r0;
307 4194816 : v_8(s[i]) = s0;
308 4194816 : v_8(t[i]) = t0;
309 : }
310 18 : }
311 :
312 : /*
313 : * GEN6 (hexa parity with Cauchy matrix) 8bit C implementation
314 : *
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.
319 : */
320 18 : void raid_gen6_int8(int nd, size_t size, void **vv)
321 : {
322 18 : uint8_t **v = (uint8_t **)vv;
323 : uint8_t *p;
324 : uint8_t *q;
325 : uint8_t *r;
326 : uint8_t *s;
327 : uint8_t *t;
328 : uint8_t *u;
329 : int d, l;
330 : size_t i;
331 :
332 : uint8_t d0, u0, t0, s0, r0, q0, p0;
333 :
334 18 : l = nd - 1;
335 18 : p = v[nd];
336 18 : q = v[nd + 1];
337 18 : r = v[nd + 2];
338 18 : s = v[nd + 3];
339 18 : t = v[nd + 4];
340 18 : u = v[nd + 5];
341 :
342 4194834 : for (i = 0; i < size; i += 1) {
343 4194816 : p0 = q0 = r0 = s0 = t0 = u0 = 0;
344 33562880 : for (d = l; d > 0; --d) {
345 29368064 : d0 = v_8(v[d][i]);
346 :
347 29368064 : p0 ^= d0;
348 29368064 : q0 ^= gfmul[d0][gfgen[1][d]];
349 29368064 : r0 ^= gfmul[d0][gfgen[2][d]];
350 29368064 : s0 ^= gfmul[d0][gfgen[3][d]];
351 29368064 : t0 ^= gfmul[d0][gfgen[4][d]];
352 29368064 : u0 ^= gfmul[d0][gfgen[5][d]];
353 : }
354 :
355 : /* first disk with all coefficients at 1 */
356 4194816 : d0 = v_8(v[0][i]);
357 :
358 4194816 : p0 ^= d0;
359 4194816 : q0 ^= d0;
360 4194816 : r0 ^= d0;
361 4194816 : s0 ^= d0;
362 4194816 : t0 ^= d0;
363 4194816 : u0 ^= d0;
364 :
365 4194816 : v_8(p[i]) = p0;
366 4194816 : v_8(q[i]) = q0;
367 4194816 : v_8(r[i]) = r0;
368 4194816 : v_8(s[i]) = s0;
369 4194816 : v_8(t[i]) = t0;
370 4194816 : v_8(u[i]) = u0;
371 : }
372 18 : }
373 :
374 : /*
375 : * Recover failure of one data block at index id[0] using parity at index
376 : * ip[0] for any RAID level.
377 : *
378 : * Starting from the equation:
379 : *
380 : * Pd = A[ip[0],id[0]] * Dx
381 : *
382 : * and solving we get:
383 : *
384 : * Dx = A[ip[0],id[0]]^-1 * Pd
385 : */
386 164 : void raid_rec1_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
387 : {
388 164 : uint8_t **v = (uint8_t **)vv;
389 : uint8_t *p;
390 : uint8_t *pa;
391 : const uint8_t *T;
392 : uint8_t G;
393 : uint8_t V;
394 : size_t i;
395 :
396 : (void)nr; /* unused, it's always 1 */
397 :
398 : /* if it's RAID5 uses the faster function */
399 164 : if (ip[0] == 0) {
400 24 : raid_rec1of1(id, nd, size, vv);
401 24 : return;
402 : }
403 :
404 : /* setup the coefficients matrix */
405 280 : G = A(ip[0], id[0]);
406 :
407 : /* invert it to solve the system of linear equations */
408 280 : V = inv(G);
409 :
410 : /* get multiplication tables */
411 280 : T = table(V);
412 :
413 : /* compute delta parity */
414 140 : raid_delta_gen(1, id, ip, nd, size, vv);
415 :
416 140 : p = v[nd + ip[0]];
417 140 : pa = v[id[0]];
418 :
419 14701708 : for (i = 0; i < size; ++i) {
420 : /* delta */
421 14701568 : uint8_t Pd = p[i] ^ pa[i];
422 :
423 : /* reconstruct */
424 14701568 : pa[i] = T[Pd];
425 : }
426 : }
427 :
428 : /*
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.
431 : *
432 : * Starting from the equations:
433 : *
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
436 : *
437 : * we solve inverting the coefficients matrix.
438 : */
439 1220 : void raid_rec2_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
440 1220 : {
441 1220 : uint8_t **v = (uint8_t **)vv;
442 : uint8_t *p;
443 : uint8_t *pa;
444 : uint8_t *q;
445 : uint8_t *qa;
446 1220 : const int N = 2;
447 1220 : const uint8_t *T[N][N];
448 1220 : uint8_t G[N * N];
449 1220 : uint8_t V[N * N];
450 : size_t i;
451 : int j, k;
452 :
453 : (void)nr; /* unused, it's always 2 */
454 :
455 : /* if it's RAID6 recovering with P and Q uses the faster function */
456 1220 : if (ip[0] == 0 && ip[1] == 1) {
457 132 : raid_rec2of2_int8(id, ip, nd, size, vv);
458 132 : return;
459 : }
460 :
461 : /* setup the coefficients matrix */
462 3264 : for (j = 0; j < N; ++j)
463 6528 : for (k = 0; k < N; ++k)
464 8704 : G[j * N + k] = A(ip[j], id[k]);
465 :
466 : /* invert it to solve the system of linear equations */
467 1088 : raid_invert(G, V, N);
468 :
469 : /* get multiplication tables */
470 3264 : for (j = 0; j < N; ++j)
471 6528 : for (k = 0; k < N; ++k)
472 8704 : T[j][k] = table(V[j * N + k]);
473 :
474 : /* compute delta parity */
475 1088 : raid_delta_gen(2, id, ip, nd, size, vv);
476 :
477 1088 : p = v[nd + ip[0]];
478 1088 : q = v[nd + ip[1]];
479 1088 : pa = v[id[0]];
480 1088 : qa = v[id[1]];
481 :
482 8660032 : for (i = 0; i < size; ++i) {
483 : /* delta */
484 8658944 : uint8_t Pd = p[i] ^ pa[i];
485 8658944 : uint8_t Qd = q[i] ^ qa[i];
486 :
487 : /* reconstruct */
488 8658944 : pa[i] = T[0][0][Pd] ^ T[0][1][Qd];
489 8658944 : qa[i] = T[1][0][Pd] ^ T[1][1][Qd];
490 : }
491 : }
492 :
493 : /*
494 : * Recover failure of N data blocks at indexes id[N] using parity at indexes
495 : * ip[N] for any RAID level.
496 : *
497 : * Starting from the N equations, with 0<=i<N :
498 : *
499 : * PD[i] = sum(A[ip[i],id[j]] * D[i]) 0<=j<N
500 : *
501 : * we solve inverting the coefficients matrix.
502 : *
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, ...
506 : */
507 17849 : void raid_recX_int8(int nr, int *id, int *ip, int nd, size_t size, void **vv)
508 : {
509 17849 : 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];
515 : size_t i;
516 : int j, k;
517 :
518 : /* setup the coefficients matrix */
519 91289 : for (j = 0; j < nr; ++j)
520 388636 : for (k = 0; k < nr; ++k)
521 630392 : G[j * nr + k] = A(ip[j], id[k]);
522 :
523 : /* invert it to solve the system of linear equations */
524 17849 : raid_invert(G, V, nr);
525 :
526 : /* get multiplication tables */
527 91289 : for (j = 0; j < nr; ++j)
528 388636 : for (k = 0; k < nr; ++k)
529 630392 : T[j][k] = table(V[j * nr + k]);
530 :
531 : /* compute delta parity */
532 17849 : raid_delta_gen(nr, id, ip, nd, size, vv);
533 :
534 91289 : for (j = 0; j < nr; ++j) {
535 73440 : p[j] = v[nd + ip[j]];
536 73440 : pa[j] = v[id[j]];
537 : }
538 :
539 38108857 : for (i = 0; i < size; ++i) {
540 : uint8_t PD[RAID_PARITY_MAX];
541 :
542 : /* delta */
543 207739136 : for (j = 0; j < nr; ++j)
544 169648128 : PD[j] = p[j][i] ^ pa[j][i];
545 :
546 : /* reconstruct */
547 207739136 : for (j = 0; j < nr; ++j) {
548 169648128 : uint8_t b = 0;
549 :
550 971054080 : for (k = 0; k < nr; ++k)
551 801405952 : b ^= T[j][k][PD[k]];
552 169648128 : pa[j][i] = b;
553 : }
554 : }
555 17849 : }
556 :
|
