1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21 /*
22 * Copyright (C) 2016 Gvozden Nešković. All rights reserved.
23 */
24
25 #ifndef _VDEV_RAIDZ_MATH_IMPL_H
26 #define _VDEV_RAIDZ_MATH_IMPL_H
27
28 #include <sys/types.h>
29
30 #define raidz_inline inline __attribute__((always_inline))
31 #ifndef noinline
32 #define noinline __attribute__((noinline))
33 #endif
34
35 /*
36 * Functions calculate multiplication constants for data reconstruction.
37 * Coefficients depend on RAIDZ geometry, indexes of failed child vdevs, and
38 * used parity columns for reconstruction.
39 * @rm RAIDZ map
40 * @tgtidx array of missing data indexes
41 * @coeff output array of coefficients. Array must be provided by
42 * user and must hold minimum MUL_CNT values.
43 */
44 static noinline void
raidz_rec_q_coeff(const raidz_map_t * rm,const int * tgtidx,unsigned * coeff)45 raidz_rec_q_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
46 {
47 const unsigned ncols = raidz_ncols(rm);
48 const unsigned x = tgtidx[TARGET_X];
49
50 coeff[MUL_Q_X] = gf_exp2(255 - (ncols - x - 1));
51 }
52
53 static noinline void
raidz_rec_r_coeff(const raidz_map_t * rm,const int * tgtidx,unsigned * coeff)54 raidz_rec_r_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
55 {
56 const unsigned ncols = raidz_ncols(rm);
57 const unsigned x = tgtidx[TARGET_X];
58
59 coeff[MUL_R_X] = gf_exp4(255 - (ncols - x - 1));
60 }
61
62 static noinline void
raidz_rec_pq_coeff(const raidz_map_t * rm,const int * tgtidx,unsigned * coeff)63 raidz_rec_pq_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
64 {
65 const unsigned ncols = raidz_ncols(rm);
66 const unsigned x = tgtidx[TARGET_X];
67 const unsigned y = tgtidx[TARGET_Y];
68 gf_t a, b, e;
69
70 a = gf_exp2(x + 255 - y);
71 b = gf_exp2(255 - (ncols - x - 1));
72 e = a ^ 0x01;
73
74 coeff[MUL_PQ_X] = gf_div(a, e);
75 coeff[MUL_PQ_Y] = gf_div(b, e);
76 }
77
78 static noinline void
raidz_rec_pr_coeff(const raidz_map_t * rm,const int * tgtidx,unsigned * coeff)79 raidz_rec_pr_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
80 {
81 const unsigned ncols = raidz_ncols(rm);
82 const unsigned x = tgtidx[TARGET_X];
83 const unsigned y = tgtidx[TARGET_Y];
84
85 gf_t a, b, e;
86
87 a = gf_exp4(x + 255 - y);
88 b = gf_exp4(255 - (ncols - x - 1));
89 e = a ^ 0x01;
90
91 coeff[MUL_PR_X] = gf_div(a, e);
92 coeff[MUL_PR_Y] = gf_div(b, e);
93 }
94
95 static noinline void
raidz_rec_qr_coeff(const raidz_map_t * rm,const int * tgtidx,unsigned * coeff)96 raidz_rec_qr_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
97 {
98 const unsigned ncols = raidz_ncols(rm);
99 const unsigned x = tgtidx[TARGET_X];
100 const unsigned y = tgtidx[TARGET_Y];
101
102 gf_t nx, ny, nxxy, nxyy, d;
103
104 nx = gf_exp2(ncols - x - 1);
105 ny = gf_exp2(ncols - y - 1);
106 nxxy = gf_mul(gf_mul(nx, nx), ny);
107 nxyy = gf_mul(gf_mul(nx, ny), ny);
108 d = nxxy ^ nxyy;
109
110 coeff[MUL_QR_XQ] = ny;
111 coeff[MUL_QR_X] = gf_div(ny, d);
112 coeff[MUL_QR_YQ] = nx;
113 coeff[MUL_QR_Y] = gf_div(nx, d);
114 }
115
116 static noinline void
raidz_rec_pqr_coeff(const raidz_map_t * rm,const int * tgtidx,unsigned * coeff)117 raidz_rec_pqr_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
118 {
119 const unsigned ncols = raidz_ncols(rm);
120 const unsigned x = tgtidx[TARGET_X];
121 const unsigned y = tgtidx[TARGET_Y];
122 const unsigned z = tgtidx[TARGET_Z];
123
124 gf_t nx, ny, nz, nxx, nyy, nzz, nyyz, nyzz, xd, yd;
125
126 nx = gf_exp2(ncols - x - 1);
127 ny = gf_exp2(ncols - y - 1);
128 nz = gf_exp2(ncols - z - 1);
129
130 nxx = gf_exp4(ncols - x - 1);
131 nyy = gf_exp4(ncols - y - 1);
132 nzz = gf_exp4(ncols - z - 1);
133
134 nyyz = gf_mul(gf_mul(ny, nz), ny);
135 nyzz = gf_mul(nzz, ny);
136
137 xd = gf_mul(nxx, ny) ^ gf_mul(nx, nyy) ^ nyyz ^
138 gf_mul(nxx, nz) ^ gf_mul(nzz, nx) ^ nyzz;
139
140 yd = gf_inv(ny ^ nz);
141
142 coeff[MUL_PQR_XP] = gf_div(nyyz ^ nyzz, xd);
143 coeff[MUL_PQR_XQ] = gf_div(nyy ^ nzz, xd);
144 coeff[MUL_PQR_XR] = gf_div(ny ^ nz, xd);
145 coeff[MUL_PQR_YU] = nx;
146 coeff[MUL_PQR_YP] = gf_mul(nz, yd);
147 coeff[MUL_PQR_YQ] = yd;
148 }
149
150 /*
151 * Method for zeroing a buffer (can be implemented using SIMD).
152 * This method is used by multiple for gen/rec functions.
153 *
154 * @dc Destination buffer
155 * @dsize Destination buffer size
156 * @private Unused
157 */
158 static int
raidz_zero_abd_cb(void * dc,size_t dsize,void * private)159 raidz_zero_abd_cb(void *dc, size_t dsize, void *private)
160 {
161 v_t *dst = (v_t *)dc;
162 size_t i;
163
164 ZERO_DEFINE();
165
166 (void) private; /* unused */
167
168 ZERO(ZERO_D);
169
170 for (i = 0; i < dsize / sizeof (v_t); i += (2 * ZERO_STRIDE)) {
171 STORE(dst + i, ZERO_D);
172 STORE(dst + i + ZERO_STRIDE, ZERO_D);
173 }
174
175 return (0);
176 }
177
178 #define raidz_zero(dabd, size) \
179 { \
180 abd_iterate_func(dabd, 0, size, raidz_zero_abd_cb, NULL); \
181 }
182
183 /*
184 * Method for copying two buffers (can be implemented using SIMD).
185 * This method is used by multiple for gen/rec functions.
186 *
187 * @dc Destination buffer
188 * @sc Source buffer
189 * @dsize Destination buffer size
190 * @ssize Source buffer size
191 * @private Unused
192 */
193 static int
raidz_copy_abd_cb(void * dc,void * sc,size_t size,void * private)194 raidz_copy_abd_cb(void *dc, void *sc, size_t size, void *private)
195 {
196 v_t *dst = (v_t *)dc;
197 const v_t *src = (v_t *)sc;
198 size_t i;
199
200 COPY_DEFINE();
201
202 (void) private; /* unused */
203
204 for (i = 0; i < size / sizeof (v_t); i += (2 * COPY_STRIDE)) {
205 LOAD(src + i, COPY_D);
206 STORE(dst + i, COPY_D);
207
208 LOAD(src + i + COPY_STRIDE, COPY_D);
209 STORE(dst + i + COPY_STRIDE, COPY_D);
210 }
211
212 return (0);
213 }
214
215
216 #define raidz_copy(dabd, sabd, size) \
217 { \
218 abd_iterate_func2(dabd, sabd, 0, 0, size, raidz_copy_abd_cb, NULL);\
219 }
220
221 /*
222 * Method for adding (XORing) two buffers.
223 * Source and destination are XORed together and result is stored in
224 * destination buffer. This method is used by multiple for gen/rec functions.
225 *
226 * @dc Destination buffer
227 * @sc Source buffer
228 * @dsize Destination buffer size
229 * @ssize Source buffer size
230 * @private Unused
231 */
232 static int
raidz_add_abd_cb(void * dc,void * sc,size_t size,void * private)233 raidz_add_abd_cb(void *dc, void *sc, size_t size, void *private)
234 {
235 v_t *dst = (v_t *)dc;
236 const v_t *src = (v_t *)sc;
237 size_t i;
238
239 ADD_DEFINE();
240
241 (void) private; /* unused */
242
243 for (i = 0; i < size / sizeof (v_t); i += (2 * ADD_STRIDE)) {
244 LOAD(dst + i, ADD_D);
245 XOR_ACC(src + i, ADD_D);
246 STORE(dst + i, ADD_D);
247
248 LOAD(dst + i + ADD_STRIDE, ADD_D);
249 XOR_ACC(src + i + ADD_STRIDE, ADD_D);
250 STORE(dst + i + ADD_STRIDE, ADD_D);
251 }
252
253 return (0);
254 }
255
256 #define raidz_add(dabd, sabd, size) \
257 { \
258 abd_iterate_func2(dabd, sabd, 0, 0, size, raidz_add_abd_cb, NULL);\
259 }
260
261 /*
262 * Method for multiplying a buffer with a constant in GF(2^8).
263 * Symbols from buffer are multiplied by a constant and result is stored
264 * back in the same buffer.
265 *
266 * @dc In/Out data buffer.
267 * @size Size of the buffer
268 * @private pointer to the multiplication constant (unsigned)
269 */
270 static int
raidz_mul_abd_cb(void * dc,size_t size,void * private)271 raidz_mul_abd_cb(void *dc, size_t size, void *private)
272 {
273 const unsigned mul = *((unsigned *)private);
274 v_t *d = (v_t *)dc;
275 size_t i;
276
277 MUL_DEFINE();
278
279 for (i = 0; i < size / sizeof (v_t); i += (2 * MUL_STRIDE)) {
280 LOAD(d + i, MUL_D);
281 MUL(mul, MUL_D);
282 STORE(d + i, MUL_D);
283
284 LOAD(d + i + MUL_STRIDE, MUL_D);
285 MUL(mul, MUL_D);
286 STORE(d + i + MUL_STRIDE, MUL_D);
287 }
288
289 return (0);
290 }
291
292
293 /*
294 * Syndrome generation/update macros
295 *
296 * Require LOAD(), XOR(), STORE(), MUL2(), and MUL4() macros
297 */
298 #define P_D_SYNDROME(D, T, t) \
299 { \
300 LOAD((t), T); \
301 XOR(D, T); \
302 STORE((t), T); \
303 }
304
305 #define Q_D_SYNDROME(D, T, t) \
306 { \
307 LOAD((t), T); \
308 MUL2(T); \
309 XOR(D, T); \
310 STORE((t), T); \
311 }
312
313 #define Q_SYNDROME(T, t) \
314 { \
315 LOAD((t), T); \
316 MUL2(T); \
317 STORE((t), T); \
318 }
319
320 #define R_D_SYNDROME(D, T, t) \
321 { \
322 LOAD((t), T); \
323 MUL4(T); \
324 XOR(D, T); \
325 STORE((t), T); \
326 }
327
328 #define R_SYNDROME(T, t) \
329 { \
330 LOAD((t), T); \
331 MUL4(T); \
332 STORE((t), T); \
333 }
334
335
336 /*
337 * PARITY CALCULATION
338 *
339 * Macros *_SYNDROME are used for parity/syndrome calculation.
340 * *_D_SYNDROME() macros are used to calculate syndrome between 0 and
341 * length of data column, and *_SYNDROME() macros are only for updating
342 * the parity/syndrome if data column is shorter.
343 *
344 * P parity is calculated using raidz_add_abd().
345 */
346
347 /*
348 * Generate P parity (RAIDZ1)
349 *
350 * @rm RAIDZ map
351 */
352 static raidz_inline void
raidz_generate_p_impl(raidz_map_t * const rm)353 raidz_generate_p_impl(raidz_map_t * const rm)
354 {
355 size_t c;
356 const size_t ncols = raidz_ncols(rm);
357 const size_t psize = rm->rm_col[CODE_P].rc_size;
358 abd_t *pabd = rm->rm_col[CODE_P].rc_abd;
359 size_t size;
360 abd_t *dabd;
361
362 raidz_math_begin();
363
364 /* start with first data column */
365 raidz_copy(pabd, rm->rm_col[1].rc_abd, psize);
366
367 for (c = 2; c < ncols; c++) {
368 dabd = rm->rm_col[c].rc_abd;
369 size = rm->rm_col[c].rc_size;
370
371 /* add data column */
372 raidz_add(pabd, dabd, size);
373 }
374
375 raidz_math_end();
376 }
377
378
379 /*
380 * Generate PQ parity (RAIDZ2)
381 * The function is called per data column.
382 *
383 * @c array of pointers to parity (code) columns
384 * @dc pointer to data column
385 * @csize size of parity columns
386 * @dsize size of data column
387 */
388 static void
raidz_gen_pq_add(void ** c,const void * dc,const size_t csize,const size_t dsize)389 raidz_gen_pq_add(void **c, const void *dc, const size_t csize,
390 const size_t dsize)
391 {
392 v_t *p = (v_t *)c[0];
393 v_t *q = (v_t *)c[1];
394 const v_t *d = (const v_t *)dc;
395 const v_t * const dend = d + (dsize / sizeof (v_t));
396 const v_t * const qend = q + (csize / sizeof (v_t));
397
398 GEN_PQ_DEFINE();
399
400 MUL2_SETUP();
401
402 for (; d < dend; d += GEN_PQ_STRIDE, p += GEN_PQ_STRIDE,
403 q += GEN_PQ_STRIDE) {
404 LOAD(d, GEN_PQ_D);
405 P_D_SYNDROME(GEN_PQ_D, GEN_PQ_C, p);
406 Q_D_SYNDROME(GEN_PQ_D, GEN_PQ_C, q);
407 }
408 for (; q < qend; q += GEN_PQ_STRIDE) {
409 Q_SYNDROME(GEN_PQ_C, q);
410 }
411 }
412
413
414 /*
415 * Generate PQ parity (RAIDZ2)
416 *
417 * @rm RAIDZ map
418 */
419 static raidz_inline void
raidz_generate_pq_impl(raidz_map_t * const rm)420 raidz_generate_pq_impl(raidz_map_t * const rm)
421 {
422 size_t c;
423 const size_t ncols = raidz_ncols(rm);
424 const size_t csize = rm->rm_col[CODE_P].rc_size;
425 size_t dsize;
426 abd_t *dabd;
427 abd_t *cabds[] = {
428 rm->rm_col[CODE_P].rc_abd,
429 rm->rm_col[CODE_Q].rc_abd
430 };
431
432 raidz_math_begin();
433
434 raidz_copy(cabds[CODE_P], rm->rm_col[2].rc_abd, csize);
435 raidz_copy(cabds[CODE_Q], rm->rm_col[2].rc_abd, csize);
436
437 for (c = 3; c < ncols; c++) {
438 dabd = rm->rm_col[c].rc_abd;
439 dsize = rm->rm_col[c].rc_size;
440
441 abd_raidz_gen_iterate(cabds, dabd, csize, dsize, 2,
442 raidz_gen_pq_add);
443 }
444
445 raidz_math_end();
446 }
447
448
449 /*
450 * Generate PQR parity (RAIDZ3)
451 * The function is called per data column.
452 *
453 * @c array of pointers to parity (code) columns
454 * @dc pointer to data column
455 * @csize size of parity columns
456 * @dsize size of data column
457 */
458 static void
raidz_gen_pqr_add(void ** c,const void * dc,const size_t csize,const size_t dsize)459 raidz_gen_pqr_add(void **c, const void *dc, const size_t csize,
460 const size_t dsize)
461 {
462 v_t *p = (v_t *)c[0];
463 v_t *q = (v_t *)c[1];
464 v_t *r = (v_t *)c[CODE_R];
465 const v_t *d = (const v_t *)dc;
466 const v_t * const dend = d + (dsize / sizeof (v_t));
467 const v_t * const qend = q + (csize / sizeof (v_t));
468
469 GEN_PQR_DEFINE();
470
471 MUL2_SETUP();
472
473 for (; d < dend; d += GEN_PQR_STRIDE, p += GEN_PQR_STRIDE,
474 q += GEN_PQR_STRIDE, r += GEN_PQR_STRIDE) {
475 LOAD(d, GEN_PQR_D);
476 P_D_SYNDROME(GEN_PQR_D, GEN_PQR_C, p);
477 Q_D_SYNDROME(GEN_PQR_D, GEN_PQR_C, q);
478 R_D_SYNDROME(GEN_PQR_D, GEN_PQR_C, r);
479 }
480 for (; q < qend; q += GEN_PQR_STRIDE, r += GEN_PQR_STRIDE) {
481 Q_SYNDROME(GEN_PQR_C, q);
482 R_SYNDROME(GEN_PQR_C, r);
483 }
484 }
485
486
487 /*
488 * Generate PQR parity (RAIDZ2)
489 *
490 * @rm RAIDZ map
491 */
492 static raidz_inline void
raidz_generate_pqr_impl(raidz_map_t * const rm)493 raidz_generate_pqr_impl(raidz_map_t * const rm)
494 {
495 size_t c;
496 const size_t ncols = raidz_ncols(rm);
497 const size_t csize = rm->rm_col[CODE_P].rc_size;
498 size_t dsize;
499 abd_t *dabd;
500 abd_t *cabds[] = {
501 rm->rm_col[CODE_P].rc_abd,
502 rm->rm_col[CODE_Q].rc_abd,
503 rm->rm_col[CODE_R].rc_abd
504 };
505
506 raidz_math_begin();
507
508 raidz_copy(cabds[CODE_P], rm->rm_col[3].rc_abd, csize);
509 raidz_copy(cabds[CODE_Q], rm->rm_col[3].rc_abd, csize);
510 raidz_copy(cabds[CODE_R], rm->rm_col[3].rc_abd, csize);
511
512 for (c = 4; c < ncols; c++) {
513 dabd = rm->rm_col[c].rc_abd;
514 dsize = rm->rm_col[c].rc_size;
515
516 abd_raidz_gen_iterate(cabds, dabd, csize, dsize, 3,
517 raidz_gen_pqr_add);
518 }
519
520 raidz_math_end();
521 }
522
523
524 /*
525 * DATA RECONSTRUCTION
526 *
527 * Data reconstruction process consists of two phases:
528 * - Syndrome calculation
529 * - Data reconstruction
530 *
531 * Syndrome is calculated by generating parity using available data columns
532 * and zeros in places of erasure. Existing parity is added to corresponding
533 * syndrome value to obtain the [P|Q|R]syn values from equation:
534 * P = Psyn + Dx + Dy + Dz
535 * Q = Qsyn + 2^x * Dx + 2^y * Dy + 2^z * Dz
536 * R = Rsyn + 4^x * Dx + 4^y * Dy + 4^z * Dz
537 *
538 * For data reconstruction phase, the corresponding equations are solved
539 * for missing data (Dx, Dy, Dz). This generally involves multiplying known
540 * symbols by an coefficient and adding them together. The multiplication
541 * constant coefficients are calculated ahead of the operation in
542 * raidz_rec_[q|r|pq|pq|qr|pqr]_coeff() functions.
543 *
544 * IMPLEMENTATION NOTE: RAID-Z block can have complex geometry, with "big"
545 * and "short" columns.
546 * For this reason, reconstruction is performed in minimum of
547 * two steps. First, from offset 0 to short_size, then from short_size to
548 * short_size. Calculation functions REC_[*]_BLOCK() are implemented to work
549 * over both ranges. The split also enables removal of conditional expressions
550 * from loop bodies, improving throughput of SIMD implementations.
551 * For the best performance, all functions marked with raidz_inline attribute
552 * must be inlined by compiler.
553 *
554 * parity data
555 * columns columns
556 * <----------> <------------------>
557 * x y <----+ missing columns (x, y)
558 * | |
559 * +---+---+---+---+-v-+---+-v-+---+ ^ 0
560 * | | | | | | | | | |
561 * | | | | | | | | | |
562 * | P | Q | R | D | D | D | D | D | |
563 * | | | | 0 | 1 | 2 | 3 | 4 | |
564 * | | | | | | | | | v
565 * | | | | | +---+---+---+ ^ short_size
566 * | | | | | | |
567 * +---+---+---+---+---+ v big_size
568 * <------------------> <---------->
569 * big columns short columns
570 *
571 */
572
573
574
575
576 /*
577 * Reconstruct single data column using P parity
578 *
579 * @syn_method raidz_add_abd()
580 * @rec_method not applicable
581 *
582 * @rm RAIDZ map
583 * @tgtidx array of missing data indexes
584 */
585 static raidz_inline int
raidz_reconstruct_p_impl(raidz_map_t * rm,const int * tgtidx)586 raidz_reconstruct_p_impl(raidz_map_t *rm, const int *tgtidx)
587 {
588 size_t c;
589 const size_t firstdc = raidz_parity(rm);
590 const size_t ncols = raidz_ncols(rm);
591 const size_t x = tgtidx[TARGET_X];
592 const size_t xsize = rm->rm_col[x].rc_size;
593 abd_t *xabd = rm->rm_col[x].rc_abd;
594 size_t size;
595 abd_t *dabd;
596
597 raidz_math_begin();
598
599 /* copy P into target */
600 raidz_copy(xabd, rm->rm_col[CODE_P].rc_abd, xsize);
601
602 /* generate p_syndrome */
603 for (c = firstdc; c < ncols; c++) {
604 if (c == x)
605 continue;
606
607 dabd = rm->rm_col[c].rc_abd;
608 size = MIN(rm->rm_col[c].rc_size, xsize);
609
610 raidz_add(xabd, dabd, size);
611 }
612
613 raidz_math_end();
614
615 return (1 << CODE_P);
616 }
617
618
619 /*
620 * Generate Q syndrome (Qsyn)
621 *
622 * @xc array of pointers to syndrome columns
623 * @dc data column (NULL if missing)
624 * @xsize size of syndrome columns
625 * @dsize size of data column (0 if missing)
626 */
627 static void
raidz_syn_q_abd(void ** xc,const void * dc,const size_t xsize,const size_t dsize)628 raidz_syn_q_abd(void **xc, const void *dc, const size_t xsize,
629 const size_t dsize)
630 {
631 v_t *x = (v_t *)xc[TARGET_X];
632 const v_t *d = (const v_t *)dc;
633 const v_t * const dend = d + (dsize / sizeof (v_t));
634 const v_t * const xend = x + (xsize / sizeof (v_t));
635
636 SYN_Q_DEFINE();
637
638 MUL2_SETUP();
639
640 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE) {
641 LOAD(d, SYN_Q_D);
642 Q_D_SYNDROME(SYN_Q_D, SYN_Q_X, x);
643 }
644 for (; x < xend; x += SYN_STRIDE) {
645 Q_SYNDROME(SYN_Q_X, x);
646 }
647 }
648
649
650 /*
651 * Reconstruct single data column using Q parity
652 *
653 * @syn_method raidz_add_abd()
654 * @rec_method raidz_mul_abd_cb()
655 *
656 * @rm RAIDZ map
657 * @tgtidx array of missing data indexes
658 */
659 static raidz_inline int
raidz_reconstruct_q_impl(raidz_map_t * rm,const int * tgtidx)660 raidz_reconstruct_q_impl(raidz_map_t *rm, const int *tgtidx)
661 {
662 size_t c;
663 size_t dsize;
664 abd_t *dabd;
665 const size_t firstdc = raidz_parity(rm);
666 const size_t ncols = raidz_ncols(rm);
667 const size_t x = tgtidx[TARGET_X];
668 abd_t *xabd = rm->rm_col[x].rc_abd;
669 const size_t xsize = rm->rm_col[x].rc_size;
670 abd_t *tabds[] = { xabd };
671
672 unsigned coeff[MUL_CNT];
673 raidz_rec_q_coeff(rm, tgtidx, coeff);
674
675 raidz_math_begin();
676
677 /* Start with first data column if present */
678 if (firstdc != x) {
679 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
680 } else {
681 raidz_zero(xabd, xsize);
682 }
683
684 /* generate q_syndrome */
685 for (c = firstdc+1; c < ncols; c++) {
686 if (c == x) {
687 dabd = NULL;
688 dsize = 0;
689 } else {
690 dabd = rm->rm_col[c].rc_abd;
691 dsize = rm->rm_col[c].rc_size;
692 }
693
694 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 1,
695 raidz_syn_q_abd);
696 }
697
698 /* add Q to the syndrome */
699 raidz_add(xabd, rm->rm_col[CODE_Q].rc_abd, xsize);
700
701 /* transform the syndrome */
702 abd_iterate_func(xabd, 0, xsize, raidz_mul_abd_cb, (void*) coeff);
703
704 raidz_math_end();
705
706 return (1 << CODE_Q);
707 }
708
709
710 /*
711 * Generate R syndrome (Rsyn)
712 *
713 * @xc array of pointers to syndrome columns
714 * @dc data column (NULL if missing)
715 * @tsize size of syndrome columns
716 * @dsize size of data column (0 if missing)
717 */
718 static void
raidz_syn_r_abd(void ** xc,const void * dc,const size_t tsize,const size_t dsize)719 raidz_syn_r_abd(void **xc, const void *dc, const size_t tsize,
720 const size_t dsize)
721 {
722 v_t *x = (v_t *)xc[TARGET_X];
723 const v_t *d = (const v_t *)dc;
724 const v_t * const dend = d + (dsize / sizeof (v_t));
725 const v_t * const xend = x + (tsize / sizeof (v_t));
726
727 SYN_R_DEFINE();
728
729 MUL2_SETUP();
730
731 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE) {
732 LOAD(d, SYN_R_D);
733 R_D_SYNDROME(SYN_R_D, SYN_R_X, x);
734 }
735 for (; x < xend; x += SYN_STRIDE) {
736 R_SYNDROME(SYN_R_X, x);
737 }
738 }
739
740
741 /*
742 * Reconstruct single data column using R parity
743 *
744 * @syn_method raidz_add_abd()
745 * @rec_method raidz_mul_abd_cb()
746 *
747 * @rm RAIDZ map
748 * @tgtidx array of missing data indexes
749 */
750 static raidz_inline int
raidz_reconstruct_r_impl(raidz_map_t * rm,const int * tgtidx)751 raidz_reconstruct_r_impl(raidz_map_t *rm, const int *tgtidx)
752 {
753 size_t c;
754 size_t dsize;
755 abd_t *dabd;
756 const size_t firstdc = raidz_parity(rm);
757 const size_t ncols = raidz_ncols(rm);
758 const size_t x = tgtidx[TARGET_X];
759 const size_t xsize = rm->rm_col[x].rc_size;
760 abd_t *xabd = rm->rm_col[x].rc_abd;
761 abd_t *tabds[] = { xabd };
762
763 unsigned coeff[MUL_CNT];
764 raidz_rec_r_coeff(rm, tgtidx, coeff);
765
766 raidz_math_begin();
767
768 /* Start with first data column if present */
769 if (firstdc != x) {
770 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
771 } else {
772 raidz_zero(xabd, xsize);
773 }
774
775
776 /* generate q_syndrome */
777 for (c = firstdc+1; c < ncols; c++) {
778 if (c == x) {
779 dabd = NULL;
780 dsize = 0;
781 } else {
782 dabd = rm->rm_col[c].rc_abd;
783 dsize = rm->rm_col[c].rc_size;
784 }
785
786 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 1,
787 raidz_syn_r_abd);
788 }
789
790 /* add R to the syndrome */
791 raidz_add(xabd, rm->rm_col[CODE_R].rc_abd, xsize);
792
793 /* transform the syndrome */
794 abd_iterate_func(xabd, 0, xsize, raidz_mul_abd_cb, (void *)coeff);
795
796 raidz_math_end();
797
798 return (1 << CODE_R);
799 }
800
801
802 /*
803 * Generate P and Q syndromes
804 *
805 * @xc array of pointers to syndrome columns
806 * @dc data column (NULL if missing)
807 * @tsize size of syndrome columns
808 * @dsize size of data column (0 if missing)
809 */
810 static void
raidz_syn_pq_abd(void ** tc,const void * dc,const size_t tsize,const size_t dsize)811 raidz_syn_pq_abd(void **tc, const void *dc, const size_t tsize,
812 const size_t dsize)
813 {
814 v_t *x = (v_t *)tc[TARGET_X];
815 v_t *y = (v_t *)tc[TARGET_Y];
816 const v_t *d = (const v_t *)dc;
817 const v_t * const dend = d + (dsize / sizeof (v_t));
818 const v_t * const yend = y + (tsize / sizeof (v_t));
819
820 SYN_PQ_DEFINE();
821
822 MUL2_SETUP();
823
824 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE, y += SYN_STRIDE) {
825 LOAD(d, SYN_PQ_D);
826 P_D_SYNDROME(SYN_PQ_D, SYN_PQ_X, x);
827 Q_D_SYNDROME(SYN_PQ_D, SYN_PQ_X, y);
828 }
829 for (; y < yend; y += SYN_STRIDE) {
830 Q_SYNDROME(SYN_PQ_X, y);
831 }
832 }
833
834 /*
835 * Reconstruct data using PQ parity and PQ syndromes
836 *
837 * @tc syndrome/result columns
838 * @tsize size of syndrome/result columns
839 * @c parity columns
840 * @mul array of multiplication constants
841 */
842 static void
raidz_rec_pq_abd(void ** tc,const size_t tsize,void ** c,const unsigned * mul)843 raidz_rec_pq_abd(void **tc, const size_t tsize, void **c,
844 const unsigned *mul)
845 {
846 v_t *x = (v_t *)tc[TARGET_X];
847 v_t *y = (v_t *)tc[TARGET_Y];
848 const v_t * const xend = x + (tsize / sizeof (v_t));
849 const v_t *p = (v_t *)c[CODE_P];
850 const v_t *q = (v_t *)c[CODE_Q];
851
852 REC_PQ_DEFINE();
853
854 for (; x < xend; x += REC_PQ_STRIDE, y += REC_PQ_STRIDE,
855 p += REC_PQ_STRIDE, q += REC_PQ_STRIDE) {
856 LOAD(x, REC_PQ_X);
857 LOAD(y, REC_PQ_Y);
858
859 XOR_ACC(p, REC_PQ_X);
860 XOR_ACC(q, REC_PQ_Y);
861
862 /* Save Pxy */
863 COPY(REC_PQ_X, REC_PQ_T);
864
865 /* Calc X */
866 MUL(mul[MUL_PQ_X], REC_PQ_X);
867 MUL(mul[MUL_PQ_Y], REC_PQ_Y);
868 XOR(REC_PQ_Y, REC_PQ_X);
869 STORE(x, REC_PQ_X);
870
871 /* Calc Y */
872 XOR(REC_PQ_T, REC_PQ_X);
873 STORE(y, REC_PQ_X);
874 }
875 }
876
877
878 /*
879 * Reconstruct two data columns using PQ parity
880 *
881 * @syn_method raidz_syn_pq_abd()
882 * @rec_method raidz_rec_pq_abd()
883 *
884 * @rm RAIDZ map
885 * @tgtidx array of missing data indexes
886 */
887 static raidz_inline int
raidz_reconstruct_pq_impl(raidz_map_t * rm,const int * tgtidx)888 raidz_reconstruct_pq_impl(raidz_map_t *rm, const int *tgtidx)
889 {
890 size_t c;
891 size_t dsize;
892 abd_t *dabd;
893 const size_t firstdc = raidz_parity(rm);
894 const size_t ncols = raidz_ncols(rm);
895 const size_t x = tgtidx[TARGET_X];
896 const size_t y = tgtidx[TARGET_Y];
897 const size_t xsize = rm->rm_col[x].rc_size;
898 const size_t ysize = rm->rm_col[y].rc_size;
899 abd_t *xabd = rm->rm_col[x].rc_abd;
900 abd_t *yabd = rm->rm_col[y].rc_abd;
901 abd_t *tabds[2] = { xabd, yabd };
902 abd_t *cabds[] = {
903 rm->rm_col[CODE_P].rc_abd,
904 rm->rm_col[CODE_Q].rc_abd
905 };
906
907 unsigned coeff[MUL_CNT];
908 raidz_rec_pq_coeff(rm, tgtidx, coeff);
909
910 /*
911 * Check if some of targets is shorter then others
912 * In this case, shorter target needs to be replaced with
913 * new buffer so that syndrome can be calculated.
914 */
915 if (ysize < xsize) {
916 yabd = abd_alloc(xsize, B_FALSE);
917 tabds[1] = yabd;
918 }
919
920 raidz_math_begin();
921
922 /* Start with first data column if present */
923 if (firstdc != x) {
924 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
925 raidz_copy(yabd, rm->rm_col[firstdc].rc_abd, xsize);
926 } else {
927 raidz_zero(xabd, xsize);
928 raidz_zero(yabd, xsize);
929 }
930
931 /* generate q_syndrome */
932 for (c = firstdc+1; c < ncols; c++) {
933 if (c == x || c == y) {
934 dabd = NULL;
935 dsize = 0;
936 } else {
937 dabd = rm->rm_col[c].rc_abd;
938 dsize = rm->rm_col[c].rc_size;
939 }
940
941 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 2,
942 raidz_syn_pq_abd);
943 }
944
945 abd_raidz_rec_iterate(cabds, tabds, xsize, 2, raidz_rec_pq_abd, coeff);
946
947 /* Copy shorter targets back to the original abd buffer */
948 if (ysize < xsize)
949 raidz_copy(rm->rm_col[y].rc_abd, yabd, ysize);
950
951 raidz_math_end();
952
953 if (ysize < xsize)
954 abd_free(yabd);
955
956 return ((1 << CODE_P) | (1 << CODE_Q));
957 }
958
959
960 /*
961 * Generate P and R syndromes
962 *
963 * @xc array of pointers to syndrome columns
964 * @dc data column (NULL if missing)
965 * @tsize size of syndrome columns
966 * @dsize size of data column (0 if missing)
967 */
968 static void
raidz_syn_pr_abd(void ** c,const void * dc,const size_t tsize,const size_t dsize)969 raidz_syn_pr_abd(void **c, const void *dc, const size_t tsize,
970 const size_t dsize)
971 {
972 v_t *x = (v_t *)c[TARGET_X];
973 v_t *y = (v_t *)c[TARGET_Y];
974 const v_t *d = (const v_t *)dc;
975 const v_t * const dend = d + (dsize / sizeof (v_t));
976 const v_t * const yend = y + (tsize / sizeof (v_t));
977
978 SYN_PR_DEFINE();
979
980 MUL2_SETUP();
981
982 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE, y += SYN_STRIDE) {
983 LOAD(d, SYN_PR_D);
984 P_D_SYNDROME(SYN_PR_D, SYN_PR_X, x);
985 R_D_SYNDROME(SYN_PR_D, SYN_PR_X, y);
986 }
987 for (; y < yend; y += SYN_STRIDE) {
988 R_SYNDROME(SYN_PR_X, y);
989 }
990 }
991
992 /*
993 * Reconstruct data using PR parity and PR syndromes
994 *
995 * @tc syndrome/result columns
996 * @tsize size of syndrome/result columns
997 * @c parity columns
998 * @mul array of multiplication constants
999 */
1000 static void
raidz_rec_pr_abd(void ** t,const size_t tsize,void ** c,const unsigned * mul)1001 raidz_rec_pr_abd(void **t, const size_t tsize, void **c,
1002 const unsigned *mul)
1003 {
1004 v_t *x = (v_t *)t[TARGET_X];
1005 v_t *y = (v_t *)t[TARGET_Y];
1006 const v_t * const xend = x + (tsize / sizeof (v_t));
1007 const v_t *p = (v_t *)c[CODE_P];
1008 const v_t *q = (v_t *)c[CODE_Q];
1009
1010 REC_PR_DEFINE();
1011
1012 for (; x < xend; x += REC_PR_STRIDE, y += REC_PR_STRIDE,
1013 p += REC_PR_STRIDE, q += REC_PR_STRIDE) {
1014 LOAD(x, REC_PR_X);
1015 LOAD(y, REC_PR_Y);
1016 XOR_ACC(p, REC_PR_X);
1017 XOR_ACC(q, REC_PR_Y);
1018
1019 /* Save Pxy */
1020 COPY(REC_PR_X, REC_PR_T);
1021
1022 /* Calc X */
1023 MUL(mul[MUL_PR_X], REC_PR_X);
1024 MUL(mul[MUL_PR_Y], REC_PR_Y);
1025 XOR(REC_PR_Y, REC_PR_X);
1026 STORE(x, REC_PR_X);
1027
1028 /* Calc Y */
1029 XOR(REC_PR_T, REC_PR_X);
1030 STORE(y, REC_PR_X);
1031 }
1032 }
1033
1034
1035 /*
1036 * Reconstruct two data columns using PR parity
1037 *
1038 * @syn_method raidz_syn_pr_abd()
1039 * @rec_method raidz_rec_pr_abd()
1040 *
1041 * @rm RAIDZ map
1042 * @tgtidx array of missing data indexes
1043 */
1044 static raidz_inline int
raidz_reconstruct_pr_impl(raidz_map_t * rm,const int * tgtidx)1045 raidz_reconstruct_pr_impl(raidz_map_t *rm, const int *tgtidx)
1046 {
1047 size_t c;
1048 size_t dsize;
1049 abd_t *dabd;
1050 const size_t firstdc = raidz_parity(rm);
1051 const size_t ncols = raidz_ncols(rm);
1052 const size_t x = tgtidx[0];
1053 const size_t y = tgtidx[1];
1054 const size_t xsize = rm->rm_col[x].rc_size;
1055 const size_t ysize = rm->rm_col[y].rc_size;
1056 abd_t *xabd = rm->rm_col[x].rc_abd;
1057 abd_t *yabd = rm->rm_col[y].rc_abd;
1058 abd_t *tabds[2] = { xabd, yabd };
1059 abd_t *cabds[] = {
1060 rm->rm_col[CODE_P].rc_abd,
1061 rm->rm_col[CODE_R].rc_abd
1062 };
1063 unsigned coeff[MUL_CNT];
1064 raidz_rec_pr_coeff(rm, tgtidx, coeff);
1065
1066 /*
1067 * Check if some of targets are shorter then others.
1068 * They need to be replaced with a new buffer so that syndrome can
1069 * be calculated on full length.
1070 */
1071 if (ysize < xsize) {
1072 yabd = abd_alloc(xsize, B_FALSE);
1073 tabds[1] = yabd;
1074 }
1075
1076 raidz_math_begin();
1077
1078 /* Start with first data column if present */
1079 if (firstdc != x) {
1080 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
1081 raidz_copy(yabd, rm->rm_col[firstdc].rc_abd, xsize);
1082 } else {
1083 raidz_zero(xabd, xsize);
1084 raidz_zero(yabd, xsize);
1085 }
1086
1087 /* generate q_syndrome */
1088 for (c = firstdc+1; c < ncols; c++) {
1089 if (c == x || c == y) {
1090 dabd = NULL;
1091 dsize = 0;
1092 } else {
1093 dabd = rm->rm_col[c].rc_abd;
1094 dsize = rm->rm_col[c].rc_size;
1095 }
1096
1097 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 2,
1098 raidz_syn_pr_abd);
1099 }
1100
1101 abd_raidz_rec_iterate(cabds, tabds, xsize, 2, raidz_rec_pr_abd, coeff);
1102
1103 /*
1104 * Copy shorter targets back to the original abd buffer
1105 */
1106 if (ysize < xsize)
1107 raidz_copy(rm->rm_col[y].rc_abd, yabd, ysize);
1108
1109 raidz_math_end();
1110
1111 if (ysize < xsize)
1112 abd_free(yabd);
1113
1114 return ((1 << CODE_P) | (1 << CODE_Q));
1115 }
1116
1117
1118 /*
1119 * Generate Q and R syndromes
1120 *
1121 * @xc array of pointers to syndrome columns
1122 * @dc data column (NULL if missing)
1123 * @tsize size of syndrome columns
1124 * @dsize size of data column (0 if missing)
1125 */
1126 static void
raidz_syn_qr_abd(void ** c,const void * dc,const size_t tsize,const size_t dsize)1127 raidz_syn_qr_abd(void **c, const void *dc, const size_t tsize,
1128 const size_t dsize)
1129 {
1130 v_t *x = (v_t *)c[TARGET_X];
1131 v_t *y = (v_t *)c[TARGET_Y];
1132 const v_t * const xend = x + (tsize / sizeof (v_t));
1133 const v_t *d = (const v_t *)dc;
1134 const v_t * const dend = d + (dsize / sizeof (v_t));
1135
1136 SYN_QR_DEFINE();
1137
1138 MUL2_SETUP();
1139
1140 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE, y += SYN_STRIDE) {
1141 LOAD(d, SYN_PQ_D);
1142 Q_D_SYNDROME(SYN_QR_D, SYN_QR_X, x);
1143 R_D_SYNDROME(SYN_QR_D, SYN_QR_X, y);
1144 }
1145 for (; x < xend; x += SYN_STRIDE, y += SYN_STRIDE) {
1146 Q_SYNDROME(SYN_QR_X, x);
1147 R_SYNDROME(SYN_QR_X, y);
1148 }
1149 }
1150
1151
1152 /*
1153 * Reconstruct data using QR parity and QR syndromes
1154 *
1155 * @tc syndrome/result columns
1156 * @tsize size of syndrome/result columns
1157 * @c parity columns
1158 * @mul array of multiplication constants
1159 */
1160 static void
raidz_rec_qr_abd(void ** t,const size_t tsize,void ** c,const unsigned * mul)1161 raidz_rec_qr_abd(void **t, const size_t tsize, void **c,
1162 const unsigned *mul)
1163 {
1164 v_t *x = (v_t *)t[TARGET_X];
1165 v_t *y = (v_t *)t[TARGET_Y];
1166 const v_t * const xend = x + (tsize / sizeof (v_t));
1167 const v_t *p = (v_t *)c[CODE_P];
1168 const v_t *q = (v_t *)c[CODE_Q];
1169
1170 REC_QR_DEFINE();
1171
1172 for (; x < xend; x += REC_QR_STRIDE, y += REC_QR_STRIDE,
1173 p += REC_QR_STRIDE, q += REC_QR_STRIDE) {
1174 LOAD(x, REC_QR_X);
1175 LOAD(y, REC_QR_Y);
1176
1177 XOR_ACC(p, REC_QR_X);
1178 XOR_ACC(q, REC_QR_Y);
1179
1180 /* Save Pxy */
1181 COPY(REC_QR_X, REC_QR_T);
1182
1183 /* Calc X */
1184 MUL(mul[MUL_QR_XQ], REC_QR_X); /* X = Q * xqm */
1185 XOR(REC_QR_Y, REC_QR_X); /* X = R ^ X */
1186 MUL(mul[MUL_QR_X], REC_QR_X); /* X = X * xm */
1187 STORE(x, REC_QR_X);
1188
1189 /* Calc Y */
1190 MUL(mul[MUL_QR_YQ], REC_QR_T); /* X = Q * xqm */
1191 XOR(REC_QR_Y, REC_QR_T); /* X = R ^ X */
1192 MUL(mul[MUL_QR_Y], REC_QR_T); /* X = X * xm */
1193 STORE(y, REC_QR_T);
1194 }
1195 }
1196
1197
1198 /*
1199 * Reconstruct two data columns using QR parity
1200 *
1201 * @syn_method raidz_syn_qr_abd()
1202 * @rec_method raidz_rec_qr_abd()
1203 *
1204 * @rm RAIDZ map
1205 * @tgtidx array of missing data indexes
1206 */
1207 static raidz_inline int
raidz_reconstruct_qr_impl(raidz_map_t * rm,const int * tgtidx)1208 raidz_reconstruct_qr_impl(raidz_map_t *rm, const int *tgtidx)
1209 {
1210 size_t c;
1211 size_t dsize;
1212 abd_t *dabd;
1213 const size_t firstdc = raidz_parity(rm);
1214 const size_t ncols = raidz_ncols(rm);
1215 const size_t x = tgtidx[TARGET_X];
1216 const size_t y = tgtidx[TARGET_Y];
1217 const size_t xsize = rm->rm_col[x].rc_size;
1218 const size_t ysize = rm->rm_col[y].rc_size;
1219 abd_t *xabd = rm->rm_col[x].rc_abd;
1220 abd_t *yabd = rm->rm_col[y].rc_abd;
1221 abd_t *tabds[2] = { xabd, yabd };
1222 abd_t *cabds[] = {
1223 rm->rm_col[CODE_Q].rc_abd,
1224 rm->rm_col[CODE_R].rc_abd
1225 };
1226 unsigned coeff[MUL_CNT];
1227 raidz_rec_qr_coeff(rm, tgtidx, coeff);
1228
1229 /*
1230 * Check if some of targets is shorter then others
1231 * In this case, shorter target needs to be replaced with
1232 * new buffer so that syndrome can be calculated.
1233 */
1234 if (ysize < xsize) {
1235 yabd = abd_alloc(xsize, B_FALSE);
1236 tabds[1] = yabd;
1237 }
1238
1239 raidz_math_begin();
1240
1241 /* Start with first data column if present */
1242 if (firstdc != x) {
1243 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
1244 raidz_copy(yabd, rm->rm_col[firstdc].rc_abd, xsize);
1245 } else {
1246 raidz_zero(xabd, xsize);
1247 raidz_zero(yabd, xsize);
1248 }
1249
1250 /* generate q_syndrome */
1251 for (c = firstdc+1; c < ncols; c++) {
1252 if (c == x || c == y) {
1253 dabd = NULL;
1254 dsize = 0;
1255 } else {
1256 dabd = rm->rm_col[c].rc_abd;
1257 dsize = rm->rm_col[c].rc_size;
1258 }
1259
1260 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 2,
1261 raidz_syn_qr_abd);
1262 }
1263
1264 abd_raidz_rec_iterate(cabds, tabds, xsize, 2, raidz_rec_qr_abd, coeff);
1265
1266 /*
1267 * Copy shorter targets back to the original abd buffer
1268 */
1269 if (ysize < xsize)
1270 raidz_copy(rm->rm_col[y].rc_abd, yabd, ysize);
1271
1272 raidz_math_end();
1273
1274 if (ysize < xsize)
1275 abd_free(yabd);
1276
1277
1278 return ((1 << CODE_Q) | (1 << CODE_R));
1279 }
1280
1281
1282 /*
1283 * Generate P, Q, and R syndromes
1284 *
1285 * @xc array of pointers to syndrome columns
1286 * @dc data column (NULL if missing)
1287 * @tsize size of syndrome columns
1288 * @dsize size of data column (0 if missing)
1289 */
1290 static void
raidz_syn_pqr_abd(void ** c,const void * dc,const size_t tsize,const size_t dsize)1291 raidz_syn_pqr_abd(void **c, const void *dc, const size_t tsize,
1292 const size_t dsize)
1293 {
1294 v_t *x = (v_t *)c[TARGET_X];
1295 v_t *y = (v_t *)c[TARGET_Y];
1296 v_t *z = (v_t *)c[TARGET_Z];
1297 const v_t * const yend = y + (tsize / sizeof (v_t));
1298 const v_t *d = (const v_t *)dc;
1299 const v_t * const dend = d + (dsize / sizeof (v_t));
1300
1301 SYN_PQR_DEFINE();
1302
1303 MUL2_SETUP();
1304
1305 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE, y += SYN_STRIDE,
1306 z += SYN_STRIDE) {
1307 LOAD(d, SYN_PQR_D);
1308 P_D_SYNDROME(SYN_PQR_D, SYN_PQR_X, x)
1309 Q_D_SYNDROME(SYN_PQR_D, SYN_PQR_X, y);
1310 R_D_SYNDROME(SYN_PQR_D, SYN_PQR_X, z);
1311 }
1312 for (; y < yend; y += SYN_STRIDE, z += SYN_STRIDE) {
1313 Q_SYNDROME(SYN_PQR_X, y);
1314 R_SYNDROME(SYN_PQR_X, z);
1315 }
1316 }
1317
1318
1319 /*
1320 * Reconstruct data using PRQ parity and PQR syndromes
1321 *
1322 * @tc syndrome/result columns
1323 * @tsize size of syndrome/result columns
1324 * @c parity columns
1325 * @mul array of multiplication constants
1326 */
1327 static void
raidz_rec_pqr_abd(void ** t,const size_t tsize,void ** c,const unsigned * const mul)1328 raidz_rec_pqr_abd(void **t, const size_t tsize, void **c,
1329 const unsigned * const mul)
1330 {
1331 v_t *x = (v_t *)t[TARGET_X];
1332 v_t *y = (v_t *)t[TARGET_Y];
1333 v_t *z = (v_t *)t[TARGET_Z];
1334 const v_t * const xend = x + (tsize / sizeof (v_t));
1335 const v_t *p = (v_t *)c[CODE_P];
1336 const v_t *q = (v_t *)c[CODE_Q];
1337 const v_t *r = (v_t *)c[CODE_R];
1338
1339 REC_PQR_DEFINE();
1340
1341 for (; x < xend; x += REC_PQR_STRIDE, y += REC_PQR_STRIDE,
1342 z += REC_PQR_STRIDE, p += REC_PQR_STRIDE, q += REC_PQR_STRIDE,
1343 r += REC_PQR_STRIDE) {
1344 LOAD(x, REC_PQR_X);
1345 LOAD(y, REC_PQR_Y);
1346 LOAD(z, REC_PQR_Z);
1347
1348 XOR_ACC(p, REC_PQR_X);
1349 XOR_ACC(q, REC_PQR_Y);
1350 XOR_ACC(r, REC_PQR_Z);
1351
1352 /* Save Pxyz and Qxyz */
1353 COPY(REC_PQR_X, REC_PQR_XS);
1354 COPY(REC_PQR_Y, REC_PQR_YS);
1355
1356 /* Calc X */
1357 MUL(mul[MUL_PQR_XP], REC_PQR_X); /* Xp = Pxyz * xp */
1358 MUL(mul[MUL_PQR_XQ], REC_PQR_Y); /* Xq = Qxyz * xq */
1359 XOR(REC_PQR_Y, REC_PQR_X);
1360 MUL(mul[MUL_PQR_XR], REC_PQR_Z); /* Xr = Rxyz * xr */
1361 XOR(REC_PQR_Z, REC_PQR_X); /* X = Xp + Xq + Xr */
1362 STORE(x, REC_PQR_X);
1363
1364 /* Calc Y */
1365 XOR(REC_PQR_X, REC_PQR_XS); /* Pyz = Pxyz + X */
1366 MUL(mul[MUL_PQR_YU], REC_PQR_X); /* Xq = X * upd_q */
1367 XOR(REC_PQR_X, REC_PQR_YS); /* Qyz = Qxyz + Xq */
1368 COPY(REC_PQR_XS, REC_PQR_X); /* restore Pyz */
1369 MUL(mul[MUL_PQR_YP], REC_PQR_X); /* Yp = Pyz * yp */
1370 MUL(mul[MUL_PQR_YQ], REC_PQR_YS); /* Yq = Qyz * yq */
1371 XOR(REC_PQR_X, REC_PQR_YS); /* Y = Yp + Yq */
1372 STORE(y, REC_PQR_YS);
1373
1374 /* Calc Z */
1375 XOR(REC_PQR_XS, REC_PQR_YS); /* Z = Pz = Pyz + Y */
1376 STORE(z, REC_PQR_YS);
1377 }
1378 }
1379
1380
1381 /*
1382 * Reconstruct three data columns using PQR parity
1383 *
1384 * @syn_method raidz_syn_pqr_abd()
1385 * @rec_method raidz_rec_pqr_abd()
1386 *
1387 * @rm RAIDZ map
1388 * @tgtidx array of missing data indexes
1389 */
1390 static raidz_inline int
raidz_reconstruct_pqr_impl(raidz_map_t * rm,const int * tgtidx)1391 raidz_reconstruct_pqr_impl(raidz_map_t *rm, const int *tgtidx)
1392 {
1393 size_t c;
1394 size_t dsize;
1395 abd_t *dabd;
1396 const size_t firstdc = raidz_parity(rm);
1397 const size_t ncols = raidz_ncols(rm);
1398 const size_t x = tgtidx[TARGET_X];
1399 const size_t y = tgtidx[TARGET_Y];
1400 const size_t z = tgtidx[TARGET_Z];
1401 const size_t xsize = rm->rm_col[x].rc_size;
1402 const size_t ysize = rm->rm_col[y].rc_size;
1403 const size_t zsize = rm->rm_col[z].rc_size;
1404 abd_t *xabd = rm->rm_col[x].rc_abd;
1405 abd_t *yabd = rm->rm_col[y].rc_abd;
1406 abd_t *zabd = rm->rm_col[z].rc_abd;
1407 abd_t *tabds[] = { xabd, yabd, zabd };
1408 abd_t *cabds[] = {
1409 rm->rm_col[CODE_P].rc_abd,
1410 rm->rm_col[CODE_Q].rc_abd,
1411 rm->rm_col[CODE_R].rc_abd
1412 };
1413 unsigned coeff[MUL_CNT];
1414 raidz_rec_pqr_coeff(rm, tgtidx, coeff);
1415
1416 /*
1417 * Check if some of targets is shorter then others
1418 * In this case, shorter target needs to be replaced with
1419 * new buffer so that syndrome can be calculated.
1420 */
1421 if (ysize < xsize) {
1422 yabd = abd_alloc(xsize, B_FALSE);
1423 tabds[1] = yabd;
1424 }
1425 if (zsize < xsize) {
1426 zabd = abd_alloc(xsize, B_FALSE);
1427 tabds[2] = zabd;
1428 }
1429
1430 raidz_math_begin();
1431
1432 /* Start with first data column if present */
1433 if (firstdc != x) {
1434 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
1435 raidz_copy(yabd, rm->rm_col[firstdc].rc_abd, xsize);
1436 raidz_copy(zabd, rm->rm_col[firstdc].rc_abd, xsize);
1437 } else {
1438 raidz_zero(xabd, xsize);
1439 raidz_zero(yabd, xsize);
1440 raidz_zero(zabd, xsize);
1441 }
1442
1443 /* generate q_syndrome */
1444 for (c = firstdc+1; c < ncols; c++) {
1445 if (c == x || c == y || c == z) {
1446 dabd = NULL;
1447 dsize = 0;
1448 } else {
1449 dabd = rm->rm_col[c].rc_abd;
1450 dsize = rm->rm_col[c].rc_size;
1451 }
1452
1453 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 3,
1454 raidz_syn_pqr_abd);
1455 }
1456
1457 abd_raidz_rec_iterate(cabds, tabds, xsize, 3, raidz_rec_pqr_abd, coeff);
1458
1459 /*
1460 * Copy shorter targets back to the original abd buffer
1461 */
1462 if (ysize < xsize)
1463 raidz_copy(rm->rm_col[y].rc_abd, yabd, ysize);
1464 if (zsize < xsize)
1465 raidz_copy(rm->rm_col[z].rc_abd, zabd, zsize);
1466
1467 raidz_math_end();
1468
1469 if (ysize < xsize)
1470 abd_free(yabd);
1471 if (zsize < xsize)
1472 abd_free(zabd);
1473
1474 return ((1 << CODE_P) | (1 << CODE_Q) | (1 << CODE_R));
1475 }
1476
1477 #endif /* _VDEV_RAIDZ_MATH_IMPL_H */
1478