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