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.
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.
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]
22 * Copyright (C) 2016 Gvozden Nešković. All rights reserved.
25 #ifndef _VDEV_RAIDZ_MATH_IMPL_H
26 #define _VDEV_RAIDZ_MATH_IMPL_H
28 #include <sys/types.h>
30 #define raidz_inline inline __attribute__((always_inline))
32 #define noinline __attribute__((noinline))
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.
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.
45 raidz_rec_q_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
47 const unsigned ncols = raidz_ncols(rm);
48 const unsigned x = tgtidx[TARGET_X];
50 coeff[MUL_Q_X] = gf_exp2(255 - (ncols - x - 1));
54 raidz_rec_r_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
56 const unsigned ncols = raidz_ncols(rm);
57 const unsigned x = tgtidx[TARGET_X];
59 coeff[MUL_R_X] = gf_exp4(255 - (ncols - x - 1));
63 raidz_rec_pq_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
65 const unsigned ncols = raidz_ncols(rm);
66 const unsigned x = tgtidx[TARGET_X];
67 const unsigned y = tgtidx[TARGET_Y];
70 a = gf_exp2(x + 255 - y);
71 b = gf_exp2(255 - (ncols - x - 1));
74 coeff[MUL_PQ_X] = gf_div(a, e);
75 coeff[MUL_PQ_Y] = gf_div(b, e);
79 raidz_rec_pr_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
81 const unsigned ncols = raidz_ncols(rm);
82 const unsigned x = tgtidx[TARGET_X];
83 const unsigned y = tgtidx[TARGET_Y];
87 a = gf_exp4(x + 255 - y);
88 b = gf_exp4(255 - (ncols - x - 1));
91 coeff[MUL_PR_X] = gf_div(a, e);
92 coeff[MUL_PR_Y] = gf_div(b, e);
96 raidz_rec_qr_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
98 const unsigned ncols = raidz_ncols(rm);
99 const unsigned x = tgtidx[TARGET_X];
100 const unsigned y = tgtidx[TARGET_Y];
102 gf_t nx, ny, nxxy, nxyy, d;
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);
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);
117 raidz_rec_pqr_coeff(const raidz_map_t *rm, const int *tgtidx, unsigned *coeff)
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];
124 gf_t nx, ny, nz, nxx, nyy, nzz, nyyz, nyzz, xd, yd;
126 nx = gf_exp2(ncols - x - 1);
127 ny = gf_exp2(ncols - y - 1);
128 nz = gf_exp2(ncols - z - 1);
130 nxx = gf_exp4(ncols - x - 1);
131 nyy = gf_exp4(ncols - y - 1);
132 nzz = gf_exp4(ncols - z - 1);
134 nyyz = gf_mul(gf_mul(ny, nz), ny);
135 nyzz = gf_mul(nzz, ny);
137 xd = gf_mul(nxx, ny) ^ gf_mul(nx, nyy) ^ nyyz ^
138 gf_mul(nxx, nz) ^ gf_mul(nzz, nx) ^ nyzz;
140 yd = gf_inv(ny ^ nz);
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;
151 * Method for zeroing a buffer (can be implemented using SIMD).
152 * This method is used by multiple for gen/rec functions.
154 * @dc Destination buffer
155 * @dsize Destination buffer size
159 raidz_zero_abd_cb(void *dc, size_t dsize, void *private)
161 v_t *dst = (v_t *)dc;
166 (void) private; /* unused */
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);
178 #define raidz_zero(dabd, size) \
180 abd_iterate_func(dabd, 0, size, raidz_zero_abd_cb, NULL); \
184 * Method for copying two buffers (can be implemented using SIMD).
185 * This method is used by multiple for gen/rec functions.
187 * @dc Destination buffer
189 * @dsize Destination buffer size
190 * @ssize Source buffer size
194 raidz_copy_abd_cb(void *dc, void *sc, size_t size, void *private)
196 v_t *dst = (v_t *)dc;
197 const v_t *src = (v_t *)sc;
202 (void) private; /* unused */
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);
208 LOAD(src + i + COPY_STRIDE, COPY_D);
209 STORE(dst + i + COPY_STRIDE, COPY_D);
216 #define raidz_copy(dabd, sabd, size) \
218 abd_iterate_func2(dabd, sabd, 0, 0, size, raidz_copy_abd_cb, NULL);\
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.
226 * @dc Destination buffer
228 * @dsize Destination buffer size
229 * @ssize Source buffer size
233 raidz_add_abd_cb(void *dc, void *sc, size_t size, void *private)
235 v_t *dst = (v_t *)dc;
236 const v_t *src = (v_t *)sc;
241 (void) private; /* unused */
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);
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);
256 #define raidz_add(dabd, sabd, size) \
258 abd_iterate_func2(dabd, sabd, 0, 0, size, raidz_add_abd_cb, NULL);\
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.
266 * @dc In/Out data buffer.
267 * @size Size of the buffer
268 * @private pointer to the multiplication constant (unsigned)
271 raidz_mul_abd_cb(void *dc, size_t size, void *private)
273 const unsigned mul = *((unsigned *)private);
279 for (i = 0; i < size / sizeof (v_t); i += (2 * MUL_STRIDE)) {
284 LOAD(d + i + MUL_STRIDE, MUL_D);
286 STORE(d + i + MUL_STRIDE, MUL_D);
294 * Syndrome generation/update macros
296 * Require LOAD(), XOR(), STORE(), MUL2(), and MUL4() macros
298 #define P_D_SYNDROME(D, T, t) \
305 #define Q_D_SYNDROME(D, T, t) \
313 #define Q_SYNDROME(T, t) \
320 #define R_D_SYNDROME(D, T, t) \
328 #define R_SYNDROME(T, t) \
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.
344 * P parity is calculated using raidz_add_abd().
348 * Generate P parity (RAIDZ1)
352 static raidz_inline void
353 raidz_generate_p_impl(raidz_map_t * const rm)
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;
364 /* start with first data column */
365 raidz_copy(pabd, rm->rm_col[1].rc_abd, psize);
367 for (c = 2; c < ncols; c++) {
368 dabd = rm->rm_col[c].rc_abd;
369 size = rm->rm_col[c].rc_size;
371 /* add data column */
372 raidz_add(pabd, dabd, size);
380 * Generate PQ parity (RAIDZ2)
381 * The function is called per data column.
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
389 raidz_gen_pq_add(void **c, const void *dc, const size_t csize,
392 v_t *p = (v_t *)c[0];
393 v_t *q = (v_t *)c[1];
394 const v_t *d = (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));
402 for (; d < dend; d += GEN_PQ_STRIDE, p += GEN_PQ_STRIDE,
403 q += GEN_PQ_STRIDE) {
405 P_D_SYNDROME(GEN_PQ_D, GEN_PQ_C, p);
406 Q_D_SYNDROME(GEN_PQ_D, GEN_PQ_C, q);
408 for (; q < qend; q += GEN_PQ_STRIDE) {
409 Q_SYNDROME(GEN_PQ_C, q);
415 * Generate PQ parity (RAIDZ2)
419 static raidz_inline void
420 raidz_generate_pq_impl(raidz_map_t * const rm)
423 const size_t ncols = raidz_ncols(rm);
424 const size_t csize = rm->rm_col[CODE_P].rc_size;
428 rm->rm_col[CODE_P].rc_abd,
429 rm->rm_col[CODE_Q].rc_abd
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);
437 for (c = 3; c < ncols; c++) {
438 dabd = rm->rm_col[c].rc_abd;
439 dsize = rm->rm_col[c].rc_size;
441 abd_raidz_gen_iterate(cabds, dabd, csize, dsize, 2,
450 * Generate PQR parity (RAIDZ3)
451 * The function is called per data column.
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
459 raidz_gen_pqr_add(void **c, const void *dc, const size_t csize,
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 = (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));
473 for (; d < dend; d += GEN_PQR_STRIDE, p += GEN_PQR_STRIDE,
474 q += GEN_PQR_STRIDE, r += GEN_PQR_STRIDE) {
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);
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);
488 * Generate PQR parity (RAIDZ2)
492 static raidz_inline void
493 raidz_generate_pqr_impl(raidz_map_t * const rm)
496 const size_t ncols = raidz_ncols(rm);
497 const size_t csize = rm->rm_col[CODE_P].rc_size;
501 rm->rm_col[CODE_P].rc_abd,
502 rm->rm_col[CODE_Q].rc_abd,
503 rm->rm_col[CODE_R].rc_abd
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);
512 for (c = 4; c < ncols; c++) {
513 dabd = rm->rm_col[c].rc_abd;
514 dsize = rm->rm_col[c].rc_size;
516 abd_raidz_gen_iterate(cabds, dabd, csize, dsize, 3,
525 * DATA RECONSTRUCTION
527 * Data reconstruction process consists of two phases:
528 * - Syndrome calculation
529 * - Data reconstruction
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
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.
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.
556 * <----------> <------------------>
557 * x y <----+ missing columns (x, y)
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
567 * +---+---+---+---+---+ v big_size
568 * <------------------> <---------->
569 * big columns short columns
577 * Reconstruct single data column using P parity
579 * @syn_method raidz_add_abd()
580 * @rec_method not applicable
583 * @tgtidx array of missing data indexes
585 static raidz_inline int
586 raidz_reconstruct_p_impl(raidz_map_t *rm, const int *tgtidx)
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;
599 /* copy P into target */
600 raidz_copy(xabd, rm->rm_col[CODE_P].rc_abd, xsize);
602 /* generate p_syndrome */
603 for (c = firstdc; c < ncols; c++) {
607 dabd = rm->rm_col[c].rc_abd;
608 size = MIN(rm->rm_col[c].rc_size, xsize);
610 raidz_add(xabd, dabd, size);
615 return (1 << CODE_P);
620 * Generate Q syndrome (Qsyn)
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)
628 raidz_syn_q_abd(void **xc, const void *dc, const size_t xsize,
631 v_t *x = (v_t *)xc[TARGET_X];
632 const v_t *d = (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));
640 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE) {
642 Q_D_SYNDROME(SYN_Q_D, SYN_Q_X, x);
644 for (; x < xend; x += SYN_STRIDE) {
645 Q_SYNDROME(SYN_Q_X, x);
651 * Reconstruct single data column using Q parity
653 * @syn_method raidz_add_abd()
654 * @rec_method raidz_mul_abd_cb()
657 * @tgtidx array of missing data indexes
659 static raidz_inline int
660 raidz_reconstruct_q_impl(raidz_map_t *rm, const int *tgtidx)
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 };
672 unsigned coeff[MUL_CNT];
673 raidz_rec_q_coeff(rm, tgtidx, coeff);
677 /* Start with first data column if present */
679 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
681 raidz_zero(xabd, xsize);
684 /* generate q_syndrome */
685 for (c = firstdc+1; c < ncols; c++) {
690 dabd = rm->rm_col[c].rc_abd;
691 dsize = rm->rm_col[c].rc_size;
694 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 1,
698 /* add Q to the syndrome */
699 raidz_add(xabd, rm->rm_col[CODE_Q].rc_abd, xsize);
701 /* transform the syndrome */
702 abd_iterate_func(xabd, 0, xsize, raidz_mul_abd_cb, (void*) coeff);
706 return (1 << CODE_Q);
711 * Generate R syndrome (Rsyn)
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)
719 raidz_syn_r_abd(void **xc, const void *dc, const size_t tsize,
722 v_t *x = (v_t *)xc[TARGET_X];
723 const v_t *d = (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));
731 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE) {
733 R_D_SYNDROME(SYN_R_D, SYN_R_X, x);
735 for (; x < xend; x += SYN_STRIDE) {
736 R_SYNDROME(SYN_R_X, x);
742 * Reconstruct single data column using R parity
744 * @syn_method raidz_add_abd()
745 * @rec_method raidz_mul_abd_cb()
748 * @tgtidx array of missing data indexes
750 static raidz_inline int
751 raidz_reconstruct_r_impl(raidz_map_t *rm, const int *tgtidx)
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 };
763 unsigned coeff[MUL_CNT];
764 raidz_rec_r_coeff(rm, tgtidx, coeff);
768 /* Start with first data column if present */
770 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
772 raidz_zero(xabd, xsize);
776 /* generate q_syndrome */
777 for (c = firstdc+1; c < ncols; c++) {
782 dabd = rm->rm_col[c].rc_abd;
783 dsize = rm->rm_col[c].rc_size;
786 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 1,
790 /* add R to the syndrome */
791 raidz_add(xabd, rm->rm_col[CODE_R].rc_abd, xsize);
793 /* transform the syndrome */
794 abd_iterate_func(xabd, 0, xsize, raidz_mul_abd_cb, (void *)coeff);
798 return (1 << CODE_R);
803 * Generate P and Q syndromes
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)
811 raidz_syn_pq_abd(void **tc, const void *dc, const size_t tsize,
814 v_t *x = (v_t *)tc[TARGET_X];
815 v_t *y = (v_t *)tc[TARGET_Y];
816 const v_t *d = (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));
824 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE, y += SYN_STRIDE) {
826 P_D_SYNDROME(SYN_PQ_D, SYN_PQ_X, x);
827 Q_D_SYNDROME(SYN_PQ_D, SYN_PQ_X, y);
829 for (; y < yend; y += SYN_STRIDE) {
830 Q_SYNDROME(SYN_PQ_X, y);
835 * Reconstruct data using PQ parity and PQ syndromes
837 * @tc syndrome/result columns
838 * @tsize size of syndrome/result columns
840 * @mul array of multiplication constants
843 raidz_rec_pq_abd(void **tc, const size_t tsize, void **c,
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];
854 for (; x < xend; x += REC_PQ_STRIDE, y += REC_PQ_STRIDE,
855 p += REC_PQ_STRIDE, q += REC_PQ_STRIDE) {
859 XOR_ACC(p, REC_PQ_X);
860 XOR_ACC(q, REC_PQ_Y);
863 COPY(REC_PQ_X, REC_PQ_T);
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);
872 XOR(REC_PQ_T, REC_PQ_X);
879 * Reconstruct two data columns using PQ parity
881 * @syn_method raidz_syn_pq_abd()
882 * @rec_method raidz_rec_pq_abd()
885 * @tgtidx array of missing data indexes
887 static raidz_inline int
888 raidz_reconstruct_pq_impl(raidz_map_t *rm, const int *tgtidx)
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 };
903 rm->rm_col[CODE_P].rc_abd,
904 rm->rm_col[CODE_Q].rc_abd
907 unsigned coeff[MUL_CNT];
908 raidz_rec_pq_coeff(rm, tgtidx, coeff);
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.
916 yabd = abd_alloc(xsize, B_FALSE);
922 /* Start with first data column if present */
924 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
925 raidz_copy(yabd, rm->rm_col[firstdc].rc_abd, xsize);
927 raidz_zero(xabd, xsize);
928 raidz_zero(yabd, xsize);
931 /* generate q_syndrome */
932 for (c = firstdc+1; c < ncols; c++) {
933 if (c == x || c == y) {
937 dabd = rm->rm_col[c].rc_abd;
938 dsize = rm->rm_col[c].rc_size;
941 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 2,
945 abd_raidz_rec_iterate(cabds, tabds, xsize, 2, raidz_rec_pq_abd, coeff);
947 /* Copy shorter targets back to the original abd buffer */
949 raidz_copy(rm->rm_col[y].rc_abd, yabd, ysize);
956 return ((1 << CODE_P) | (1 << CODE_Q));
961 * Generate P and R syndromes
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)
969 raidz_syn_pr_abd(void **c, const void *dc, const size_t tsize,
972 v_t *x = (v_t *)c[TARGET_X];
973 v_t *y = (v_t *)c[TARGET_Y];
974 const v_t *d = (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));
982 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE, y += SYN_STRIDE) {
984 P_D_SYNDROME(SYN_PR_D, SYN_PR_X, x);
985 R_D_SYNDROME(SYN_PR_D, SYN_PR_X, y);
987 for (; y < yend; y += SYN_STRIDE) {
988 R_SYNDROME(SYN_PR_X, y);
993 * Reconstruct data using PR parity and PR syndromes
995 * @tc syndrome/result columns
996 * @tsize size of syndrome/result columns
998 * @mul array of multiplication constants
1001 raidz_rec_pr_abd(void **t, const size_t tsize, void **c,
1002 const unsigned *mul)
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];
1012 for (; x < xend; x += REC_PR_STRIDE, y += REC_PR_STRIDE,
1013 p += REC_PR_STRIDE, q += REC_PR_STRIDE) {
1016 XOR_ACC(p, REC_PR_X);
1017 XOR_ACC(q, REC_PR_Y);
1020 COPY(REC_PR_X, REC_PR_T);
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);
1029 XOR(REC_PR_T, REC_PR_X);
1036 * Reconstruct two data columns using PR parity
1038 * @syn_method raidz_syn_pr_abd()
1039 * @rec_method raidz_rec_pr_abd()
1042 * @tgtidx array of missing data indexes
1044 static raidz_inline int
1045 raidz_reconstruct_pr_impl(raidz_map_t *rm, const int *tgtidx)
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 };
1060 rm->rm_col[CODE_P].rc_abd,
1061 rm->rm_col[CODE_R].rc_abd
1063 unsigned coeff[MUL_CNT];
1064 raidz_rec_pr_coeff(rm, tgtidx, coeff);
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.
1071 if (ysize < xsize) {
1072 yabd = abd_alloc(xsize, B_FALSE);
1078 /* Start with first data column if present */
1080 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
1081 raidz_copy(yabd, rm->rm_col[firstdc].rc_abd, xsize);
1083 raidz_zero(xabd, xsize);
1084 raidz_zero(yabd, xsize);
1087 /* generate q_syndrome */
1088 for (c = firstdc+1; c < ncols; c++) {
1089 if (c == x || c == y) {
1093 dabd = rm->rm_col[c].rc_abd;
1094 dsize = rm->rm_col[c].rc_size;
1097 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 2,
1101 abd_raidz_rec_iterate(cabds, tabds, xsize, 2, raidz_rec_pr_abd, coeff);
1104 * Copy shorter targets back to the original abd buffer
1107 raidz_copy(rm->rm_col[y].rc_abd, yabd, ysize);
1114 return ((1 << CODE_P) | (1 << CODE_Q));
1119 * Generate Q and R syndromes
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)
1127 raidz_syn_qr_abd(void **c, const void *dc, const size_t tsize,
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 = (v_t *)dc;
1134 const v_t * const dend = d + (dsize / sizeof (v_t));
1140 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE, y += SYN_STRIDE) {
1142 Q_D_SYNDROME(SYN_QR_D, SYN_QR_X, x);
1143 R_D_SYNDROME(SYN_QR_D, SYN_QR_X, y);
1145 for (; x < xend; x += SYN_STRIDE, y += SYN_STRIDE) {
1146 Q_SYNDROME(SYN_QR_X, x);
1147 R_SYNDROME(SYN_QR_X, y);
1153 * Reconstruct data using QR parity and QR syndromes
1155 * @tc syndrome/result columns
1156 * @tsize size of syndrome/result columns
1158 * @mul array of multiplication constants
1161 raidz_rec_qr_abd(void **t, const size_t tsize, void **c,
1162 const unsigned *mul)
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];
1172 for (; x < xend; x += REC_QR_STRIDE, y += REC_QR_STRIDE,
1173 p += REC_QR_STRIDE, q += REC_QR_STRIDE) {
1177 XOR_ACC(p, REC_QR_X);
1178 XOR_ACC(q, REC_QR_Y);
1181 COPY(REC_QR_X, REC_QR_T);
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 */
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 */
1199 * Reconstruct two data columns using QR parity
1201 * @syn_method raidz_syn_qr_abd()
1202 * @rec_method raidz_rec_qr_abd()
1205 * @tgtidx array of missing data indexes
1207 static raidz_inline int
1208 raidz_reconstruct_qr_impl(raidz_map_t *rm, const int *tgtidx)
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 };
1223 rm->rm_col[CODE_Q].rc_abd,
1224 rm->rm_col[CODE_R].rc_abd
1226 unsigned coeff[MUL_CNT];
1227 raidz_rec_qr_coeff(rm, tgtidx, coeff);
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.
1234 if (ysize < xsize) {
1235 yabd = abd_alloc(xsize, B_FALSE);
1241 /* Start with first data column if present */
1243 raidz_copy(xabd, rm->rm_col[firstdc].rc_abd, xsize);
1244 raidz_copy(yabd, rm->rm_col[firstdc].rc_abd, xsize);
1246 raidz_zero(xabd, xsize);
1247 raidz_zero(yabd, xsize);
1250 /* generate q_syndrome */
1251 for (c = firstdc+1; c < ncols; c++) {
1252 if (c == x || c == y) {
1256 dabd = rm->rm_col[c].rc_abd;
1257 dsize = rm->rm_col[c].rc_size;
1260 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 2,
1264 abd_raidz_rec_iterate(cabds, tabds, xsize, 2, raidz_rec_qr_abd, coeff);
1267 * Copy shorter targets back to the original abd buffer
1270 raidz_copy(rm->rm_col[y].rc_abd, yabd, ysize);
1278 return ((1 << CODE_Q) | (1 << CODE_R));
1283 * Generate P, Q, and R syndromes
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)
1291 raidz_syn_pqr_abd(void **c, const void *dc, const size_t tsize,
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 = (v_t *)dc;
1299 const v_t * const dend = d + (dsize / sizeof (v_t));
1305 for (; d < dend; d += SYN_STRIDE, x += SYN_STRIDE, y += SYN_STRIDE,
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);
1312 for (; y < yend; y += SYN_STRIDE, z += SYN_STRIDE) {
1313 Q_SYNDROME(SYN_PQR_X, y);
1314 R_SYNDROME(SYN_PQR_X, z);
1320 * Reconstruct data using PRQ parity and PQR syndromes
1322 * @tc syndrome/result columns
1323 * @tsize size of syndrome/result columns
1325 * @mul array of multiplication constants
1328 raidz_rec_pqr_abd(void **t, const size_t tsize, void **c,
1329 const unsigned * const mul)
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];
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) {
1348 XOR_ACC(p, REC_PQR_X);
1349 XOR_ACC(q, REC_PQR_Y);
1350 XOR_ACC(r, REC_PQR_Z);
1352 /* Save Pxyz and Qxyz */
1353 COPY(REC_PQR_X, REC_PQR_XS);
1354 COPY(REC_PQR_Y, REC_PQR_YS);
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);
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);
1375 XOR(REC_PQR_XS, REC_PQR_YS); /* Z = Pz = Pyz + Y */
1376 STORE(z, REC_PQR_YS);
1382 * Reconstruct three data columns using PQR parity
1384 * @syn_method raidz_syn_pqr_abd()
1385 * @rec_method raidz_rec_pqr_abd()
1388 * @tgtidx array of missing data indexes
1390 static raidz_inline int
1391 raidz_reconstruct_pqr_impl(raidz_map_t *rm, const int *tgtidx)
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 };
1409 rm->rm_col[CODE_P].rc_abd,
1410 rm->rm_col[CODE_Q].rc_abd,
1411 rm->rm_col[CODE_R].rc_abd
1413 unsigned coeff[MUL_CNT];
1414 raidz_rec_pqr_coeff(rm, tgtidx, coeff);
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.
1421 if (ysize < xsize) {
1422 yabd = abd_alloc(xsize, B_FALSE);
1425 if (zsize < xsize) {
1426 zabd = abd_alloc(xsize, B_FALSE);
1432 /* Start with first data column if present */
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);
1438 raidz_zero(xabd, xsize);
1439 raidz_zero(yabd, xsize);
1440 raidz_zero(zabd, xsize);
1443 /* generate q_syndrome */
1444 for (c = firstdc+1; c < ncols; c++) {
1445 if (c == x || c == y || c == z) {
1449 dabd = rm->rm_col[c].rc_abd;
1450 dsize = rm->rm_col[c].rc_size;
1453 abd_raidz_gen_iterate(tabds, dabd, xsize, dsize, 3,
1457 abd_raidz_rec_iterate(cabds, tabds, xsize, 3, raidz_rec_pqr_abd, coeff);
1460 * Copy shorter targets back to the original abd buffer
1463 raidz_copy(rm->rm_col[y].rc_abd, yabd, ysize);
1465 raidz_copy(rm->rm_col[z].rc_abd, zabd, zsize);
1474 return ((1 << CODE_P) | (1 << CODE_Q) | (1 << CODE_R));
1477 #endif /* _VDEV_RAIDZ_MATH_IMPL_H */