]>
git.proxmox.com Git - mirror_zfs.git/blob - module/zfs/vdev_raidz_math_impl.h
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 */