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]
23 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
24 * Copyright (c) 2012, 2019 by Delphix. All rights reserved.
25 * Copyright (c) 2016 Gvozden Nešković. All rights reserved.
28 #include <sys/zfs_context.h>
30 #include <sys/vdev_impl.h>
32 #include <sys/zio_checksum.h>
34 #include <sys/fs/zfs.h>
35 #include <sys/fm/fs/zfs.h>
36 #include <sys/vdev_raidz.h>
37 #include <sys/vdev_raidz_impl.h>
40 #include <sys/vdev.h> /* For vdev_xlate() in vdev_raidz_io_verify() */
44 * Virtual device vector for RAID-Z.
46 * This vdev supports single, double, and triple parity. For single parity,
47 * we use a simple XOR of all the data columns. For double or triple parity,
48 * we use a special case of Reed-Solomon coding. This extends the
49 * technique described in "The mathematics of RAID-6" by H. Peter Anvin by
50 * drawing on the system described in "A Tutorial on Reed-Solomon Coding for
51 * Fault-Tolerance in RAID-like Systems" by James S. Plank on which the
52 * former is also based. The latter is designed to provide higher performance
55 * Note that the Plank paper claimed to support arbitrary N+M, but was then
56 * amended six years later identifying a critical flaw that invalidates its
57 * claims. Nevertheless, the technique can be adapted to work for up to
58 * triple parity. For additional parity, the amendment "Note: Correction to
59 * the 1997 Tutorial on Reed-Solomon Coding" by James S. Plank and Ying Ding
60 * is viable, but the additional complexity means that write performance will
63 * All of the methods above operate on a Galois field, defined over the
64 * integers mod 2^N. In our case we choose N=8 for GF(8) so that all elements
65 * can be expressed with a single byte. Briefly, the operations on the
66 * field are defined as follows:
68 * o addition (+) is represented by a bitwise XOR
69 * o subtraction (-) is therefore identical to addition: A + B = A - B
70 * o multiplication of A by 2 is defined by the following bitwise expression:
75 * (A * 2)_4 = A_3 + A_7
76 * (A * 2)_3 = A_2 + A_7
77 * (A * 2)_2 = A_1 + A_7
81 * In C, multiplying by 2 is therefore ((a << 1) ^ ((a & 0x80) ? 0x1d : 0)).
82 * As an aside, this multiplication is derived from the error correcting
83 * primitive polynomial x^8 + x^4 + x^3 + x^2 + 1.
85 * Observe that any number in the field (except for 0) can be expressed as a
86 * power of 2 -- a generator for the field. We store a table of the powers of
87 * 2 and logs base 2 for quick look ups, and exploit the fact that A * B can
88 * be rewritten as 2^(log_2(A) + log_2(B)) (where '+' is normal addition rather
89 * than field addition). The inverse of a field element A (A^-1) is therefore
90 * A ^ (255 - 1) = A^254.
92 * The up-to-three parity columns, P, Q, R over several data columns,
93 * D_0, ... D_n-1, can be expressed by field operations:
95 * P = D_0 + D_1 + ... + D_n-2 + D_n-1
96 * Q = 2^n-1 * D_0 + 2^n-2 * D_1 + ... + 2^1 * D_n-2 + 2^0 * D_n-1
97 * = ((...((D_0) * 2 + D_1) * 2 + ...) * 2 + D_n-2) * 2 + D_n-1
98 * R = 4^n-1 * D_0 + 4^n-2 * D_1 + ... + 4^1 * D_n-2 + 4^0 * D_n-1
99 * = ((...((D_0) * 4 + D_1) * 4 + ...) * 4 + D_n-2) * 4 + D_n-1
101 * We chose 1, 2, and 4 as our generators because 1 corresponds to the trivial
102 * XOR operation, and 2 and 4 can be computed quickly and generate linearly-
103 * independent coefficients. (There are no additional coefficients that have
104 * this property which is why the uncorrected Plank method breaks down.)
106 * See the reconstruction code below for how P, Q and R can used individually
107 * or in concert to recover missing data columns.
110 #define VDEV_RAIDZ_P 0
111 #define VDEV_RAIDZ_Q 1
112 #define VDEV_RAIDZ_R 2
114 #define VDEV_RAIDZ_MUL_2(x) (((x) << 1) ^ (((x) & 0x80) ? 0x1d : 0))
115 #define VDEV_RAIDZ_MUL_4(x) (VDEV_RAIDZ_MUL_2(VDEV_RAIDZ_MUL_2(x)))
118 * We provide a mechanism to perform the field multiplication operation on a
119 * 64-bit value all at once rather than a byte at a time. This works by
120 * creating a mask from the top bit in each byte and using that to
121 * conditionally apply the XOR of 0x1d.
123 #define VDEV_RAIDZ_64MUL_2(x, mask) \
125 (mask) = (x) & 0x8080808080808080ULL; \
126 (mask) = ((mask) << 1) - ((mask) >> 7); \
127 (x) = (((x) << 1) & 0xfefefefefefefefeULL) ^ \
128 ((mask) & 0x1d1d1d1d1d1d1d1dULL); \
131 #define VDEV_RAIDZ_64MUL_4(x, mask) \
133 VDEV_RAIDZ_64MUL_2((x), mask); \
134 VDEV_RAIDZ_64MUL_2((x), mask); \
138 vdev_raidz_map_free(raidz_map_t *rm)
142 for (c = 0; c < rm->rm_firstdatacol; c++) {
143 abd_free(rm->rm_col[c].rc_abd);
145 if (rm->rm_col[c].rc_gdata != NULL)
146 abd_free(rm->rm_col[c].rc_gdata);
149 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++)
150 abd_put(rm->rm_col[c].rc_abd);
152 if (rm->rm_abd_copy != NULL)
153 abd_free(rm->rm_abd_copy);
155 kmem_free(rm, offsetof(raidz_map_t, rm_col[rm->rm_scols]));
159 vdev_raidz_map_free_vsd(zio_t *zio)
161 raidz_map_t *rm = zio->io_vsd;
163 ASSERT0(rm->rm_freed);
166 if (rm->rm_reports == 0)
167 vdev_raidz_map_free(rm);
172 vdev_raidz_cksum_free(void *arg, size_t ignored)
174 raidz_map_t *rm = arg;
176 ASSERT3U(rm->rm_reports, >, 0);
178 if (--rm->rm_reports == 0 && rm->rm_freed != 0)
179 vdev_raidz_map_free(rm);
183 vdev_raidz_cksum_finish(zio_cksum_report_t *zcr, const abd_t *good_data)
185 raidz_map_t *rm = zcr->zcr_cbdata;
186 const size_t c = zcr->zcr_cbinfo;
189 const abd_t *good = NULL;
190 const abd_t *bad = rm->rm_col[c].rc_abd;
192 if (good_data == NULL) {
193 zfs_ereport_finish_checksum(zcr, NULL, NULL, B_FALSE);
197 if (c < rm->rm_firstdatacol) {
199 * The first time through, calculate the parity blocks for
200 * the good data (this relies on the fact that the good
201 * data never changes for a given logical ZIO)
203 if (rm->rm_col[0].rc_gdata == NULL) {
204 abd_t *bad_parity[VDEV_RAIDZ_MAXPARITY];
207 * Set up the rm_col[]s to generate the parity for
208 * good_data, first saving the parity bufs and
209 * replacing them with buffers to hold the result.
211 for (x = 0; x < rm->rm_firstdatacol; x++) {
212 bad_parity[x] = rm->rm_col[x].rc_abd;
213 rm->rm_col[x].rc_abd =
214 rm->rm_col[x].rc_gdata =
215 abd_alloc_sametype(rm->rm_col[x].rc_abd,
216 rm->rm_col[x].rc_size);
219 /* fill in the data columns from good_data */
221 for (; x < rm->rm_cols; x++) {
222 abd_put(rm->rm_col[x].rc_abd);
224 rm->rm_col[x].rc_abd =
225 abd_get_offset_size((abd_t *)good_data,
226 offset, rm->rm_col[x].rc_size);
227 offset += rm->rm_col[x].rc_size;
231 * Construct the parity from the good data.
233 vdev_raidz_generate_parity(rm);
235 /* restore everything back to its original state */
236 for (x = 0; x < rm->rm_firstdatacol; x++)
237 rm->rm_col[x].rc_abd = bad_parity[x];
240 for (x = rm->rm_firstdatacol; x < rm->rm_cols; x++) {
241 abd_put(rm->rm_col[x].rc_abd);
242 rm->rm_col[x].rc_abd = abd_get_offset_size(
243 rm->rm_abd_copy, offset,
244 rm->rm_col[x].rc_size);
245 offset += rm->rm_col[x].rc_size;
249 ASSERT3P(rm->rm_col[c].rc_gdata, !=, NULL);
250 good = abd_get_offset_size(rm->rm_col[c].rc_gdata, 0,
251 rm->rm_col[c].rc_size);
253 /* adjust good_data to point at the start of our column */
255 for (x = rm->rm_firstdatacol; x < c; x++)
256 offset += rm->rm_col[x].rc_size;
258 good = abd_get_offset_size((abd_t *)good_data, offset,
259 rm->rm_col[c].rc_size);
262 /* we drop the ereport if it ends up that the data was good */
263 zfs_ereport_finish_checksum(zcr, good, bad, B_TRUE);
264 abd_put((abd_t *)good);
268 * Invoked indirectly by zfs_ereport_start_checksum(), called
269 * below when our read operation fails completely. The main point
270 * is to keep a copy of everything we read from disk, so that at
271 * vdev_raidz_cksum_finish() time we can compare it with the good data.
274 vdev_raidz_cksum_report(zio_t *zio, zio_cksum_report_t *zcr, void *arg)
276 size_t c = (size_t)(uintptr_t)arg;
279 raidz_map_t *rm = zio->io_vsd;
282 /* set up the report and bump the refcount */
283 zcr->zcr_cbdata = rm;
285 zcr->zcr_finish = vdev_raidz_cksum_finish;
286 zcr->zcr_free = vdev_raidz_cksum_free;
289 ASSERT3U(rm->rm_reports, >, 0);
291 if (rm->rm_abd_copy != NULL)
295 * It's the first time we're called for this raidz_map_t, so we need
296 * to copy the data aside; there's no guarantee that our zio's buffer
297 * won't be re-used for something else.
299 * Our parity data is already in separate buffers, so there's no need
304 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++)
305 size += rm->rm_col[c].rc_size;
307 rm->rm_abd_copy = abd_alloc_for_io(size, B_FALSE);
309 for (offset = 0, c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
310 raidz_col_t *col = &rm->rm_col[c];
311 abd_t *tmp = abd_get_offset_size(rm->rm_abd_copy, offset,
314 abd_copy(tmp, col->rc_abd, col->rc_size);
316 abd_put(col->rc_abd);
319 offset += col->rc_size;
321 ASSERT3U(offset, ==, size);
324 static const zio_vsd_ops_t vdev_raidz_vsd_ops = {
325 .vsd_free = vdev_raidz_map_free_vsd,
326 .vsd_cksum_report = vdev_raidz_cksum_report
330 * Divides the IO evenly across all child vdevs; usually, dcols is
331 * the number of children in the target vdev.
333 * Avoid inlining the function to keep vdev_raidz_io_start(), which
334 * is this functions only caller, as small as possible on the stack.
336 noinline raidz_map_t *
337 vdev_raidz_map_alloc(zio_t *zio, uint64_t ashift, uint64_t dcols,
341 /* The starting RAIDZ (parent) vdev sector of the block. */
342 uint64_t b = zio->io_offset >> ashift;
343 /* The zio's size in units of the vdev's minimum sector size. */
344 uint64_t s = zio->io_size >> ashift;
345 /* The first column for this stripe. */
346 uint64_t f = b % dcols;
347 /* The starting byte offset on each child vdev. */
348 uint64_t o = (b / dcols) << ashift;
349 uint64_t q, r, c, bc, col, acols, scols, coff, devidx, asize, tot;
353 * "Quotient": The number of data sectors for this stripe on all but
354 * the "big column" child vdevs that also contain "remainder" data.
356 q = s / (dcols - nparity);
359 * "Remainder": The number of partial stripe data sectors in this I/O.
360 * This will add a sector to some, but not all, child vdevs.
362 r = s - q * (dcols - nparity);
364 /* The number of "big columns" - those which contain remainder data. */
365 bc = (r == 0 ? 0 : r + nparity);
368 * The total number of data and parity sectors associated with
371 tot = s + nparity * (q + (r == 0 ? 0 : 1));
373 /* acols: The columns that will be accessed. */
374 /* scols: The columns that will be accessed or skipped. */
376 /* Our I/O request doesn't span all child vdevs. */
378 scols = MIN(dcols, roundup(bc, nparity + 1));
384 ASSERT3U(acols, <=, scols);
386 rm = kmem_alloc(offsetof(raidz_map_t, rm_col[scols]), KM_SLEEP);
389 rm->rm_scols = scols;
391 rm->rm_skipstart = bc;
392 rm->rm_missingdata = 0;
393 rm->rm_missingparity = 0;
394 rm->rm_firstdatacol = nparity;
395 rm->rm_abd_copy = NULL;
398 rm->rm_ecksuminjected = 0;
402 for (c = 0; c < scols; c++) {
407 coff += 1ULL << ashift;
409 rm->rm_col[c].rc_devidx = col;
410 rm->rm_col[c].rc_offset = coff;
411 rm->rm_col[c].rc_abd = NULL;
412 rm->rm_col[c].rc_gdata = NULL;
413 rm->rm_col[c].rc_error = 0;
414 rm->rm_col[c].rc_tried = 0;
415 rm->rm_col[c].rc_skipped = 0;
418 rm->rm_col[c].rc_size = 0;
420 rm->rm_col[c].rc_size = (q + 1) << ashift;
422 rm->rm_col[c].rc_size = q << ashift;
424 asize += rm->rm_col[c].rc_size;
427 ASSERT3U(asize, ==, tot << ashift);
428 rm->rm_asize = roundup(asize, (nparity + 1) << ashift);
429 rm->rm_nskip = roundup(tot, nparity + 1) - tot;
430 ASSERT3U(rm->rm_asize - asize, ==, rm->rm_nskip << ashift);
431 ASSERT3U(rm->rm_nskip, <=, nparity);
433 for (c = 0; c < rm->rm_firstdatacol; c++)
434 rm->rm_col[c].rc_abd =
435 abd_alloc_linear(rm->rm_col[c].rc_size, B_FALSE);
437 rm->rm_col[c].rc_abd = abd_get_offset_size(zio->io_abd, 0,
438 rm->rm_col[c].rc_size);
439 off = rm->rm_col[c].rc_size;
441 for (c = c + 1; c < acols; c++) {
442 rm->rm_col[c].rc_abd = abd_get_offset_size(zio->io_abd, off,
443 rm->rm_col[c].rc_size);
444 off += rm->rm_col[c].rc_size;
448 * If all data stored spans all columns, there's a danger that parity
449 * will always be on the same device and, since parity isn't read
450 * during normal operation, that device's I/O bandwidth won't be
451 * used effectively. We therefore switch the parity every 1MB.
453 * ... at least that was, ostensibly, the theory. As a practical
454 * matter unless we juggle the parity between all devices evenly, we
455 * won't see any benefit. Further, occasional writes that aren't a
456 * multiple of the LCM of the number of children and the minimum
457 * stripe width are sufficient to avoid pessimal behavior.
458 * Unfortunately, this decision created an implicit on-disk format
459 * requirement that we need to support for all eternity, but only
460 * for single-parity RAID-Z.
462 * If we intend to skip a sector in the zeroth column for padding
463 * we must make sure to note this swap. We will never intend to
464 * skip the first column since at least one data and one parity
465 * column must appear in each row.
467 ASSERT(rm->rm_cols >= 2);
468 ASSERT(rm->rm_col[0].rc_size == rm->rm_col[1].rc_size);
470 if (rm->rm_firstdatacol == 1 && (zio->io_offset & (1ULL << 20))) {
471 devidx = rm->rm_col[0].rc_devidx;
472 o = rm->rm_col[0].rc_offset;
473 rm->rm_col[0].rc_devidx = rm->rm_col[1].rc_devidx;
474 rm->rm_col[0].rc_offset = rm->rm_col[1].rc_offset;
475 rm->rm_col[1].rc_devidx = devidx;
476 rm->rm_col[1].rc_offset = o;
478 if (rm->rm_skipstart == 0)
479 rm->rm_skipstart = 1;
483 zio->io_vsd_ops = &vdev_raidz_vsd_ops;
485 /* init RAIDZ parity ops */
486 rm->rm_ops = vdev_raidz_math_get_ops();
498 vdev_raidz_p_func(void *buf, size_t size, void *private)
500 struct pqr_struct *pqr = private;
501 const uint64_t *src = buf;
502 int i, cnt = size / sizeof (src[0]);
504 ASSERT(pqr->p && !pqr->q && !pqr->r);
506 for (i = 0; i < cnt; i++, src++, pqr->p++)
513 vdev_raidz_pq_func(void *buf, size_t size, void *private)
515 struct pqr_struct *pqr = private;
516 const uint64_t *src = buf;
518 int i, cnt = size / sizeof (src[0]);
520 ASSERT(pqr->p && pqr->q && !pqr->r);
522 for (i = 0; i < cnt; i++, src++, pqr->p++, pqr->q++) {
524 VDEV_RAIDZ_64MUL_2(*pqr->q, mask);
532 vdev_raidz_pqr_func(void *buf, size_t size, void *private)
534 struct pqr_struct *pqr = private;
535 const uint64_t *src = buf;
537 int i, cnt = size / sizeof (src[0]);
539 ASSERT(pqr->p && pqr->q && pqr->r);
541 for (i = 0; i < cnt; i++, src++, pqr->p++, pqr->q++, pqr->r++) {
543 VDEV_RAIDZ_64MUL_2(*pqr->q, mask);
545 VDEV_RAIDZ_64MUL_4(*pqr->r, mask);
553 vdev_raidz_generate_parity_p(raidz_map_t *rm)
559 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
560 src = rm->rm_col[c].rc_abd;
561 p = abd_to_buf(rm->rm_col[VDEV_RAIDZ_P].rc_abd);
563 if (c == rm->rm_firstdatacol) {
564 abd_copy_to_buf(p, src, rm->rm_col[c].rc_size);
566 struct pqr_struct pqr = { p, NULL, NULL };
567 (void) abd_iterate_func(src, 0, rm->rm_col[c].rc_size,
568 vdev_raidz_p_func, &pqr);
574 vdev_raidz_generate_parity_pq(raidz_map_t *rm)
576 uint64_t *p, *q, pcnt, ccnt, mask, i;
580 pcnt = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (p[0]);
581 ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size ==
582 rm->rm_col[VDEV_RAIDZ_Q].rc_size);
584 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
585 src = rm->rm_col[c].rc_abd;
586 p = abd_to_buf(rm->rm_col[VDEV_RAIDZ_P].rc_abd);
587 q = abd_to_buf(rm->rm_col[VDEV_RAIDZ_Q].rc_abd);
589 ccnt = rm->rm_col[c].rc_size / sizeof (p[0]);
591 if (c == rm->rm_firstdatacol) {
592 ASSERT(ccnt == pcnt || ccnt == 0);
593 abd_copy_to_buf(p, src, rm->rm_col[c].rc_size);
594 (void) memcpy(q, p, rm->rm_col[c].rc_size);
596 for (i = ccnt; i < pcnt; i++) {
601 struct pqr_struct pqr = { p, q, NULL };
603 ASSERT(ccnt <= pcnt);
604 (void) abd_iterate_func(src, 0, rm->rm_col[c].rc_size,
605 vdev_raidz_pq_func, &pqr);
608 * Treat short columns as though they are full of 0s.
609 * Note that there's therefore nothing needed for P.
611 for (i = ccnt; i < pcnt; i++) {
612 VDEV_RAIDZ_64MUL_2(q[i], mask);
619 vdev_raidz_generate_parity_pqr(raidz_map_t *rm)
621 uint64_t *p, *q, *r, pcnt, ccnt, mask, i;
625 pcnt = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (p[0]);
626 ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size ==
627 rm->rm_col[VDEV_RAIDZ_Q].rc_size);
628 ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size ==
629 rm->rm_col[VDEV_RAIDZ_R].rc_size);
631 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
632 src = rm->rm_col[c].rc_abd;
633 p = abd_to_buf(rm->rm_col[VDEV_RAIDZ_P].rc_abd);
634 q = abd_to_buf(rm->rm_col[VDEV_RAIDZ_Q].rc_abd);
635 r = abd_to_buf(rm->rm_col[VDEV_RAIDZ_R].rc_abd);
637 ccnt = rm->rm_col[c].rc_size / sizeof (p[0]);
639 if (c == rm->rm_firstdatacol) {
640 ASSERT(ccnt == pcnt || ccnt == 0);
641 abd_copy_to_buf(p, src, rm->rm_col[c].rc_size);
642 (void) memcpy(q, p, rm->rm_col[c].rc_size);
643 (void) memcpy(r, p, rm->rm_col[c].rc_size);
645 for (i = ccnt; i < pcnt; i++) {
651 struct pqr_struct pqr = { p, q, r };
653 ASSERT(ccnt <= pcnt);
654 (void) abd_iterate_func(src, 0, rm->rm_col[c].rc_size,
655 vdev_raidz_pqr_func, &pqr);
658 * Treat short columns as though they are full of 0s.
659 * Note that there's therefore nothing needed for P.
661 for (i = ccnt; i < pcnt; i++) {
662 VDEV_RAIDZ_64MUL_2(q[i], mask);
663 VDEV_RAIDZ_64MUL_4(r[i], mask);
670 * Generate RAID parity in the first virtual columns according to the number of
671 * parity columns available.
674 vdev_raidz_generate_parity(raidz_map_t *rm)
676 /* Generate using the new math implementation */
677 if (vdev_raidz_math_generate(rm) != RAIDZ_ORIGINAL_IMPL)
680 switch (rm->rm_firstdatacol) {
682 vdev_raidz_generate_parity_p(rm);
685 vdev_raidz_generate_parity_pq(rm);
688 vdev_raidz_generate_parity_pqr(rm);
691 cmn_err(CE_PANIC, "invalid RAID-Z configuration");
697 vdev_raidz_reconst_p_func(void *dbuf, void *sbuf, size_t size, void *private)
699 uint64_t *dst = dbuf;
700 uint64_t *src = sbuf;
701 int cnt = size / sizeof (src[0]);
703 for (int i = 0; i < cnt; i++) {
712 vdev_raidz_reconst_q_pre_func(void *dbuf, void *sbuf, size_t size,
715 uint64_t *dst = dbuf;
716 uint64_t *src = sbuf;
718 int cnt = size / sizeof (dst[0]);
720 for (int i = 0; i < cnt; i++, dst++, src++) {
721 VDEV_RAIDZ_64MUL_2(*dst, mask);
730 vdev_raidz_reconst_q_pre_tail_func(void *buf, size_t size, void *private)
734 int cnt = size / sizeof (dst[0]);
736 for (int i = 0; i < cnt; i++, dst++) {
737 /* same operation as vdev_raidz_reconst_q_pre_func() on dst */
738 VDEV_RAIDZ_64MUL_2(*dst, mask);
744 struct reconst_q_struct {
750 vdev_raidz_reconst_q_post_func(void *buf, size_t size, void *private)
752 struct reconst_q_struct *rq = private;
754 int cnt = size / sizeof (dst[0]);
756 for (int i = 0; i < cnt; i++, dst++, rq->q++) {
761 for (j = 0, b = (uint8_t *)dst; j < 8; j++, b++) {
762 *b = vdev_raidz_exp2(*b, rq->exp);
769 struct reconst_pq_struct {
779 vdev_raidz_reconst_pq_func(void *xbuf, void *ybuf, size_t size, void *private)
781 struct reconst_pq_struct *rpq = private;
785 for (int i = 0; i < size;
786 i++, rpq->p++, rpq->q++, rpq->pxy++, rpq->qxy++, xd++, yd++) {
787 *xd = vdev_raidz_exp2(*rpq->p ^ *rpq->pxy, rpq->aexp) ^
788 vdev_raidz_exp2(*rpq->q ^ *rpq->qxy, rpq->bexp);
789 *yd = *rpq->p ^ *rpq->pxy ^ *xd;
796 vdev_raidz_reconst_pq_tail_func(void *xbuf, size_t size, void *private)
798 struct reconst_pq_struct *rpq = private;
801 for (int i = 0; i < size;
802 i++, rpq->p++, rpq->q++, rpq->pxy++, rpq->qxy++, xd++) {
803 /* same operation as vdev_raidz_reconst_pq_func() on xd */
804 *xd = vdev_raidz_exp2(*rpq->p ^ *rpq->pxy, rpq->aexp) ^
805 vdev_raidz_exp2(*rpq->q ^ *rpq->qxy, rpq->bexp);
812 vdev_raidz_reconstruct_p(raidz_map_t *rm, int *tgts, int ntgts)
819 ASSERT(x >= rm->rm_firstdatacol);
820 ASSERT(x < rm->rm_cols);
822 ASSERT(rm->rm_col[x].rc_size <= rm->rm_col[VDEV_RAIDZ_P].rc_size);
823 ASSERT(rm->rm_col[x].rc_size > 0);
825 src = rm->rm_col[VDEV_RAIDZ_P].rc_abd;
826 dst = rm->rm_col[x].rc_abd;
828 abd_copy_from_buf(dst, abd_to_buf(src), rm->rm_col[x].rc_size);
830 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
831 uint64_t size = MIN(rm->rm_col[x].rc_size,
832 rm->rm_col[c].rc_size);
834 src = rm->rm_col[c].rc_abd;
835 dst = rm->rm_col[x].rc_abd;
840 (void) abd_iterate_func2(dst, src, 0, 0, size,
841 vdev_raidz_reconst_p_func, NULL);
844 return (1 << VDEV_RAIDZ_P);
848 vdev_raidz_reconstruct_q(raidz_map_t *rm, int *tgts, int ntgts)
856 ASSERT(rm->rm_col[x].rc_size <= rm->rm_col[VDEV_RAIDZ_Q].rc_size);
858 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
859 uint64_t size = (c == x) ? 0 : MIN(rm->rm_col[x].rc_size,
860 rm->rm_col[c].rc_size);
862 src = rm->rm_col[c].rc_abd;
863 dst = rm->rm_col[x].rc_abd;
865 if (c == rm->rm_firstdatacol) {
866 abd_copy(dst, src, size);
867 if (rm->rm_col[x].rc_size > size)
868 abd_zero_off(dst, size,
869 rm->rm_col[x].rc_size - size);
872 ASSERT3U(size, <=, rm->rm_col[x].rc_size);
873 (void) abd_iterate_func2(dst, src, 0, 0, size,
874 vdev_raidz_reconst_q_pre_func, NULL);
875 (void) abd_iterate_func(dst,
876 size, rm->rm_col[x].rc_size - size,
877 vdev_raidz_reconst_q_pre_tail_func, NULL);
881 src = rm->rm_col[VDEV_RAIDZ_Q].rc_abd;
882 dst = rm->rm_col[x].rc_abd;
883 exp = 255 - (rm->rm_cols - 1 - x);
885 struct reconst_q_struct rq = { abd_to_buf(src), exp };
886 (void) abd_iterate_func(dst, 0, rm->rm_col[x].rc_size,
887 vdev_raidz_reconst_q_post_func, &rq);
889 return (1 << VDEV_RAIDZ_Q);
893 vdev_raidz_reconstruct_pq(raidz_map_t *rm, int *tgts, int ntgts)
895 uint8_t *p, *q, *pxy, *qxy, tmp, a, b, aexp, bexp;
896 abd_t *pdata, *qdata;
897 uint64_t xsize, ysize;
904 ASSERT(x >= rm->rm_firstdatacol);
905 ASSERT(y < rm->rm_cols);
907 ASSERT(rm->rm_col[x].rc_size >= rm->rm_col[y].rc_size);
910 * Move the parity data aside -- we're going to compute parity as
911 * though columns x and y were full of zeros -- Pxy and Qxy. We want to
912 * reuse the parity generation mechanism without trashing the actual
913 * parity so we make those columns appear to be full of zeros by
914 * setting their lengths to zero.
916 pdata = rm->rm_col[VDEV_RAIDZ_P].rc_abd;
917 qdata = rm->rm_col[VDEV_RAIDZ_Q].rc_abd;
918 xsize = rm->rm_col[x].rc_size;
919 ysize = rm->rm_col[y].rc_size;
921 rm->rm_col[VDEV_RAIDZ_P].rc_abd =
922 abd_alloc_linear(rm->rm_col[VDEV_RAIDZ_P].rc_size, B_TRUE);
923 rm->rm_col[VDEV_RAIDZ_Q].rc_abd =
924 abd_alloc_linear(rm->rm_col[VDEV_RAIDZ_Q].rc_size, B_TRUE);
925 rm->rm_col[x].rc_size = 0;
926 rm->rm_col[y].rc_size = 0;
928 vdev_raidz_generate_parity_pq(rm);
930 rm->rm_col[x].rc_size = xsize;
931 rm->rm_col[y].rc_size = ysize;
933 p = abd_to_buf(pdata);
934 q = abd_to_buf(qdata);
935 pxy = abd_to_buf(rm->rm_col[VDEV_RAIDZ_P].rc_abd);
936 qxy = abd_to_buf(rm->rm_col[VDEV_RAIDZ_Q].rc_abd);
937 xd = rm->rm_col[x].rc_abd;
938 yd = rm->rm_col[y].rc_abd;
942 * Pxy = P + D_x + D_y
943 * Qxy = Q + 2^(ndevs - 1 - x) * D_x + 2^(ndevs - 1 - y) * D_y
945 * We can then solve for D_x:
946 * D_x = A * (P + Pxy) + B * (Q + Qxy)
948 * A = 2^(x - y) * (2^(x - y) + 1)^-1
949 * B = 2^(ndevs - 1 - x) * (2^(x - y) + 1)^-1
951 * With D_x in hand, we can easily solve for D_y:
952 * D_y = P + Pxy + D_x
955 a = vdev_raidz_pow2[255 + x - y];
956 b = vdev_raidz_pow2[255 - (rm->rm_cols - 1 - x)];
957 tmp = 255 - vdev_raidz_log2[a ^ 1];
959 aexp = vdev_raidz_log2[vdev_raidz_exp2(a, tmp)];
960 bexp = vdev_raidz_log2[vdev_raidz_exp2(b, tmp)];
962 ASSERT3U(xsize, >=, ysize);
963 struct reconst_pq_struct rpq = { p, q, pxy, qxy, aexp, bexp };
965 (void) abd_iterate_func2(xd, yd, 0, 0, ysize,
966 vdev_raidz_reconst_pq_func, &rpq);
967 (void) abd_iterate_func(xd, ysize, xsize - ysize,
968 vdev_raidz_reconst_pq_tail_func, &rpq);
970 abd_free(rm->rm_col[VDEV_RAIDZ_P].rc_abd);
971 abd_free(rm->rm_col[VDEV_RAIDZ_Q].rc_abd);
974 * Restore the saved parity data.
976 rm->rm_col[VDEV_RAIDZ_P].rc_abd = pdata;
977 rm->rm_col[VDEV_RAIDZ_Q].rc_abd = qdata;
979 return ((1 << VDEV_RAIDZ_P) | (1 << VDEV_RAIDZ_Q));
984 * In the general case of reconstruction, we must solve the system of linear
985 * equations defined by the coefficients used to generate parity as well as
986 * the contents of the data and parity disks. This can be expressed with
987 * vectors for the original data (D) and the actual data (d) and parity (p)
988 * and a matrix composed of the identity matrix (I) and a dispersal matrix (V):
992 * | V | | D_0 | | p_m-1 |
993 * | | x | : | = | d_0 |
994 * | I | | D_n-1 | | : |
995 * | | ~~ ~~ | d_n-1 |
998 * I is simply a square identity matrix of size n, and V is a vandermonde
999 * matrix defined by the coefficients we chose for the various parity columns
1000 * (1, 2, 4). Note that these values were chosen both for simplicity, speedy
1001 * computation as well as linear separability.
1004 * | 1 .. 1 1 1 | | p_0 |
1005 * | 2^n-1 .. 4 2 1 | __ __ | : |
1006 * | 4^n-1 .. 16 4 1 | | D_0 | | p_m-1 |
1007 * | 1 .. 0 0 0 | | D_1 | | d_0 |
1008 * | 0 .. 0 0 0 | x | D_2 | = | d_1 |
1009 * | : : : : | | : | | d_2 |
1010 * | 0 .. 1 0 0 | | D_n-1 | | : |
1011 * | 0 .. 0 1 0 | ~~ ~~ | : |
1012 * | 0 .. 0 0 1 | | d_n-1 |
1015 * Note that I, V, d, and p are known. To compute D, we must invert the
1016 * matrix and use the known data and parity values to reconstruct the unknown
1017 * data values. We begin by removing the rows in V|I and d|p that correspond
1018 * to failed or missing columns; we then make V|I square (n x n) and d|p
1019 * sized n by removing rows corresponding to unused parity from the bottom up
1020 * to generate (V|I)' and (d|p)'. We can then generate the inverse of (V|I)'
1021 * using Gauss-Jordan elimination. In the example below we use m=3 parity
1022 * columns, n=8 data columns, with errors in d_1, d_2, and p_1:
1024 * | 1 1 1 1 1 1 1 1 |
1025 * | 128 64 32 16 8 4 2 1 | <-----+-+-- missing disks
1026 * | 19 205 116 29 64 16 4 1 | / /
1027 * | 1 0 0 0 0 0 0 0 | / /
1028 * | 0 1 0 0 0 0 0 0 | <--' /
1029 * (V|I) = | 0 0 1 0 0 0 0 0 | <---'
1030 * | 0 0 0 1 0 0 0 0 |
1031 * | 0 0 0 0 1 0 0 0 |
1032 * | 0 0 0 0 0 1 0 0 |
1033 * | 0 0 0 0 0 0 1 0 |
1034 * | 0 0 0 0 0 0 0 1 |
1037 * | 1 1 1 1 1 1 1 1 |
1038 * | 128 64 32 16 8 4 2 1 |
1039 * | 19 205 116 29 64 16 4 1 |
1040 * | 1 0 0 0 0 0 0 0 |
1041 * | 0 1 0 0 0 0 0 0 |
1042 * (V|I)' = | 0 0 1 0 0 0 0 0 |
1043 * | 0 0 0 1 0 0 0 0 |
1044 * | 0 0 0 0 1 0 0 0 |
1045 * | 0 0 0 0 0 1 0 0 |
1046 * | 0 0 0 0 0 0 1 0 |
1047 * | 0 0 0 0 0 0 0 1 |
1050 * Here we employ Gauss-Jordan elimination to find the inverse of (V|I)'. We
1051 * have carefully chosen the seed values 1, 2, and 4 to ensure that this
1052 * matrix is not singular.
1054 * | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 |
1055 * | 19 205 116 29 64 16 4 1 0 1 0 0 0 0 0 0 |
1056 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1057 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1058 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1059 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1060 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1061 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1064 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1065 * | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 |
1066 * | 19 205 116 29 64 16 4 1 0 1 0 0 0 0 0 0 |
1067 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1068 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1069 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1070 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1071 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1074 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1075 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1076 * | 0 205 116 0 0 0 0 0 0 1 19 29 64 16 4 1 |
1077 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1078 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1079 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1080 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1081 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1084 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1085 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1086 * | 0 0 185 0 0 0 0 0 205 1 222 208 141 221 201 204 |
1087 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1088 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1089 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1090 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1091 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1094 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1095 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1096 * | 0 0 1 0 0 0 0 0 166 100 4 40 158 168 216 209 |
1097 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1098 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1099 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1100 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1101 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1104 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1105 * | 0 1 0 0 0 0 0 0 167 100 5 41 159 169 217 208 |
1106 * | 0 0 1 0 0 0 0 0 166 100 4 40 158 168 216 209 |
1107 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1108 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1109 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1110 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1111 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1114 * | 0 0 1 0 0 0 0 0 |
1115 * | 167 100 5 41 159 169 217 208 |
1116 * | 166 100 4 40 158 168 216 209 |
1117 * (V|I)'^-1 = | 0 0 0 1 0 0 0 0 |
1118 * | 0 0 0 0 1 0 0 0 |
1119 * | 0 0 0 0 0 1 0 0 |
1120 * | 0 0 0 0 0 0 1 0 |
1121 * | 0 0 0 0 0 0 0 1 |
1124 * We can then simply compute D = (V|I)'^-1 x (d|p)' to discover the values
1125 * of the missing data.
1127 * As is apparent from the example above, the only non-trivial rows in the
1128 * inverse matrix correspond to the data disks that we're trying to
1129 * reconstruct. Indeed, those are the only rows we need as the others would
1130 * only be useful for reconstructing data known or assumed to be valid. For
1131 * that reason, we only build the coefficients in the rows that correspond to
1137 vdev_raidz_matrix_init(raidz_map_t *rm, int n, int nmap, int *map,
1143 ASSERT(n == rm->rm_cols - rm->rm_firstdatacol);
1146 * Fill in the missing rows of interest.
1148 for (i = 0; i < nmap; i++) {
1149 ASSERT3S(0, <=, map[i]);
1150 ASSERT3S(map[i], <=, 2);
1157 for (j = 0; j < n; j++) {
1161 rows[i][j] = vdev_raidz_pow2[pow];
1167 vdev_raidz_matrix_invert(raidz_map_t *rm, int n, int nmissing, int *missing,
1168 uint8_t **rows, uint8_t **invrows, const uint8_t *used)
1174 * Assert that the first nmissing entries from the array of used
1175 * columns correspond to parity columns and that subsequent entries
1176 * correspond to data columns.
1178 for (i = 0; i < nmissing; i++) {
1179 ASSERT3S(used[i], <, rm->rm_firstdatacol);
1181 for (; i < n; i++) {
1182 ASSERT3S(used[i], >=, rm->rm_firstdatacol);
1186 * First initialize the storage where we'll compute the inverse rows.
1188 for (i = 0; i < nmissing; i++) {
1189 for (j = 0; j < n; j++) {
1190 invrows[i][j] = (i == j) ? 1 : 0;
1195 * Subtract all trivial rows from the rows of consequence.
1197 for (i = 0; i < nmissing; i++) {
1198 for (j = nmissing; j < n; j++) {
1199 ASSERT3U(used[j], >=, rm->rm_firstdatacol);
1200 jj = used[j] - rm->rm_firstdatacol;
1202 invrows[i][j] = rows[i][jj];
1208 * For each of the rows of interest, we must normalize it and subtract
1209 * a multiple of it from the other rows.
1211 for (i = 0; i < nmissing; i++) {
1212 for (j = 0; j < missing[i]; j++) {
1213 ASSERT0(rows[i][j]);
1215 ASSERT3U(rows[i][missing[i]], !=, 0);
1218 * Compute the inverse of the first element and multiply each
1219 * element in the row by that value.
1221 log = 255 - vdev_raidz_log2[rows[i][missing[i]]];
1223 for (j = 0; j < n; j++) {
1224 rows[i][j] = vdev_raidz_exp2(rows[i][j], log);
1225 invrows[i][j] = vdev_raidz_exp2(invrows[i][j], log);
1228 for (ii = 0; ii < nmissing; ii++) {
1232 ASSERT3U(rows[ii][missing[i]], !=, 0);
1234 log = vdev_raidz_log2[rows[ii][missing[i]]];
1236 for (j = 0; j < n; j++) {
1238 vdev_raidz_exp2(rows[i][j], log);
1240 vdev_raidz_exp2(invrows[i][j], log);
1246 * Verify that the data that is left in the rows are properly part of
1247 * an identity matrix.
1249 for (i = 0; i < nmissing; i++) {
1250 for (j = 0; j < n; j++) {
1251 if (j == missing[i]) {
1252 ASSERT3U(rows[i][j], ==, 1);
1254 ASSERT0(rows[i][j]);
1261 vdev_raidz_matrix_reconstruct(raidz_map_t *rm, int n, int nmissing,
1262 int *missing, uint8_t **invrows, const uint8_t *used)
1267 uint8_t *dst[VDEV_RAIDZ_MAXPARITY] = { NULL };
1268 uint64_t dcount[VDEV_RAIDZ_MAXPARITY] = { 0 };
1272 uint8_t *invlog[VDEV_RAIDZ_MAXPARITY];
1276 psize = sizeof (invlog[0][0]) * n * nmissing;
1277 p = kmem_alloc(psize, KM_SLEEP);
1279 for (pp = p, i = 0; i < nmissing; i++) {
1284 for (i = 0; i < nmissing; i++) {
1285 for (j = 0; j < n; j++) {
1286 ASSERT3U(invrows[i][j], !=, 0);
1287 invlog[i][j] = vdev_raidz_log2[invrows[i][j]];
1291 for (i = 0; i < n; i++) {
1293 ASSERT3U(c, <, rm->rm_cols);
1295 src = abd_to_buf(rm->rm_col[c].rc_abd);
1296 ccount = rm->rm_col[c].rc_size;
1297 for (j = 0; j < nmissing; j++) {
1298 cc = missing[j] + rm->rm_firstdatacol;
1299 ASSERT3U(cc, >=, rm->rm_firstdatacol);
1300 ASSERT3U(cc, <, rm->rm_cols);
1301 ASSERT3U(cc, !=, c);
1303 dst[j] = abd_to_buf(rm->rm_col[cc].rc_abd);
1304 dcount[j] = rm->rm_col[cc].rc_size;
1307 ASSERT(ccount >= rm->rm_col[missing[0]].rc_size || i > 0);
1309 for (x = 0; x < ccount; x++, src++) {
1311 log = vdev_raidz_log2[*src];
1313 for (cc = 0; cc < nmissing; cc++) {
1314 if (x >= dcount[cc])
1320 if ((ll = log + invlog[cc][i]) >= 255)
1322 val = vdev_raidz_pow2[ll];
1333 kmem_free(p, psize);
1337 vdev_raidz_reconstruct_general(raidz_map_t *rm, int *tgts, int ntgts)
1341 int missing_rows[VDEV_RAIDZ_MAXPARITY];
1342 int parity_map[VDEV_RAIDZ_MAXPARITY];
1347 uint8_t *rows[VDEV_RAIDZ_MAXPARITY];
1348 uint8_t *invrows[VDEV_RAIDZ_MAXPARITY];
1351 abd_t **bufs = NULL;
1356 * Matrix reconstruction can't use scatter ABDs yet, so we allocate
1357 * temporary linear ABDs.
1359 if (!abd_is_linear(rm->rm_col[rm->rm_firstdatacol].rc_abd)) {
1360 bufs = kmem_alloc(rm->rm_cols * sizeof (abd_t *), KM_PUSHPAGE);
1362 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
1363 raidz_col_t *col = &rm->rm_col[c];
1365 bufs[c] = col->rc_abd;
1366 col->rc_abd = abd_alloc_linear(col->rc_size, B_TRUE);
1367 abd_copy(col->rc_abd, bufs[c], col->rc_size);
1371 n = rm->rm_cols - rm->rm_firstdatacol;
1374 * Figure out which data columns are missing.
1377 for (t = 0; t < ntgts; t++) {
1378 if (tgts[t] >= rm->rm_firstdatacol) {
1379 missing_rows[nmissing_rows++] =
1380 tgts[t] - rm->rm_firstdatacol;
1385 * Figure out which parity columns to use to help generate the missing
1388 for (tt = 0, c = 0, i = 0; i < nmissing_rows; c++) {
1390 ASSERT(c < rm->rm_firstdatacol);
1393 * Skip any targeted parity columns.
1395 if (c == tgts[tt]) {
1407 ASSERT3U(code, <, 1 << VDEV_RAIDZ_MAXPARITY);
1409 psize = (sizeof (rows[0][0]) + sizeof (invrows[0][0])) *
1410 nmissing_rows * n + sizeof (used[0]) * n;
1411 p = kmem_alloc(psize, KM_SLEEP);
1413 for (pp = p, i = 0; i < nmissing_rows; i++) {
1421 for (i = 0; i < nmissing_rows; i++) {
1422 used[i] = parity_map[i];
1425 for (tt = 0, c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
1426 if (tt < nmissing_rows &&
1427 c == missing_rows[tt] + rm->rm_firstdatacol) {
1438 * Initialize the interesting rows of the matrix.
1440 vdev_raidz_matrix_init(rm, n, nmissing_rows, parity_map, rows);
1443 * Invert the matrix.
1445 vdev_raidz_matrix_invert(rm, n, nmissing_rows, missing_rows, rows,
1449 * Reconstruct the missing data using the generated matrix.
1451 vdev_raidz_matrix_reconstruct(rm, n, nmissing_rows, missing_rows,
1454 kmem_free(p, psize);
1457 * copy back from temporary linear abds and free them
1460 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
1461 raidz_col_t *col = &rm->rm_col[c];
1463 abd_copy(bufs[c], col->rc_abd, col->rc_size);
1464 abd_free(col->rc_abd);
1465 col->rc_abd = bufs[c];
1467 kmem_free(bufs, rm->rm_cols * sizeof (abd_t *));
1474 vdev_raidz_reconstruct(raidz_map_t *rm, const int *t, int nt)
1476 int tgts[VDEV_RAIDZ_MAXPARITY], *dt;
1480 int nbadparity, nbaddata;
1481 int parity_valid[VDEV_RAIDZ_MAXPARITY];
1484 * The tgts list must already be sorted.
1486 for (i = 1; i < nt; i++) {
1487 ASSERT(t[i] > t[i - 1]);
1490 nbadparity = rm->rm_firstdatacol;
1491 nbaddata = rm->rm_cols - nbadparity;
1493 for (i = 0, c = 0; c < rm->rm_cols; c++) {
1494 if (c < rm->rm_firstdatacol)
1495 parity_valid[c] = B_FALSE;
1497 if (i < nt && c == t[i]) {
1500 } else if (rm->rm_col[c].rc_error != 0) {
1502 } else if (c >= rm->rm_firstdatacol) {
1505 parity_valid[c] = B_TRUE;
1510 ASSERT(ntgts >= nt);
1511 ASSERT(nbaddata >= 0);
1512 ASSERT(nbaddata + nbadparity == ntgts);
1514 dt = &tgts[nbadparity];
1516 /* Reconstruct using the new math implementation */
1517 ret = vdev_raidz_math_reconstruct(rm, parity_valid, dt, nbaddata);
1518 if (ret != RAIDZ_ORIGINAL_IMPL)
1522 * See if we can use any of our optimized reconstruction routines.
1526 if (parity_valid[VDEV_RAIDZ_P])
1527 return (vdev_raidz_reconstruct_p(rm, dt, 1));
1529 ASSERT(rm->rm_firstdatacol > 1);
1531 if (parity_valid[VDEV_RAIDZ_Q])
1532 return (vdev_raidz_reconstruct_q(rm, dt, 1));
1534 ASSERT(rm->rm_firstdatacol > 2);
1538 ASSERT(rm->rm_firstdatacol > 1);
1540 if (parity_valid[VDEV_RAIDZ_P] &&
1541 parity_valid[VDEV_RAIDZ_Q])
1542 return (vdev_raidz_reconstruct_pq(rm, dt, 2));
1544 ASSERT(rm->rm_firstdatacol > 2);
1549 code = vdev_raidz_reconstruct_general(rm, tgts, ntgts);
1550 ASSERT(code < (1 << VDEV_RAIDZ_MAXPARITY));
1556 vdev_raidz_open(vdev_t *vd, uint64_t *asize, uint64_t *max_asize,
1557 uint64_t *logical_ashift, uint64_t *physical_ashift)
1560 uint64_t nparity = vd->vdev_nparity;
1565 ASSERT(nparity > 0);
1567 if (nparity > VDEV_RAIDZ_MAXPARITY ||
1568 vd->vdev_children < nparity + 1) {
1569 vd->vdev_stat.vs_aux = VDEV_AUX_BAD_LABEL;
1570 return (SET_ERROR(EINVAL));
1573 vdev_open_children(vd);
1575 for (c = 0; c < vd->vdev_children; c++) {
1576 cvd = vd->vdev_child[c];
1578 if (cvd->vdev_open_error != 0) {
1579 lasterror = cvd->vdev_open_error;
1584 *asize = MIN(*asize - 1, cvd->vdev_asize - 1) + 1;
1585 *max_asize = MIN(*max_asize - 1, cvd->vdev_max_asize - 1) + 1;
1586 *logical_ashift = MAX(*logical_ashift, cvd->vdev_ashift);
1587 *physical_ashift = MAX(*physical_ashift,
1588 cvd->vdev_physical_ashift);
1591 *asize *= vd->vdev_children;
1592 *max_asize *= vd->vdev_children;
1594 if (numerrors > nparity) {
1595 vd->vdev_stat.vs_aux = VDEV_AUX_NO_REPLICAS;
1603 vdev_raidz_close(vdev_t *vd)
1607 for (c = 0; c < vd->vdev_children; c++)
1608 vdev_close(vd->vdev_child[c]);
1612 vdev_raidz_asize(vdev_t *vd, uint64_t psize)
1615 uint64_t ashift = vd->vdev_top->vdev_ashift;
1616 uint64_t cols = vd->vdev_children;
1617 uint64_t nparity = vd->vdev_nparity;
1619 asize = ((psize - 1) >> ashift) + 1;
1620 asize += nparity * ((asize + cols - nparity - 1) / (cols - nparity));
1621 asize = roundup(asize, nparity + 1) << ashift;
1627 vdev_raidz_child_done(zio_t *zio)
1629 raidz_col_t *rc = zio->io_private;
1631 rc->rc_error = zio->io_error;
1637 vdev_raidz_io_verify(zio_t *zio, raidz_map_t *rm, int col)
1640 vdev_t *vd = zio->io_vd;
1641 vdev_t *tvd = vd->vdev_top;
1643 range_seg64_t logical_rs, physical_rs;
1644 logical_rs.rs_start = zio->io_offset;
1645 logical_rs.rs_end = logical_rs.rs_start +
1646 vdev_raidz_asize(zio->io_vd, zio->io_size);
1648 raidz_col_t *rc = &rm->rm_col[col];
1649 vdev_t *cvd = vd->vdev_child[rc->rc_devidx];
1651 vdev_xlate(cvd, &logical_rs, &physical_rs);
1652 ASSERT3U(rc->rc_offset, ==, physical_rs.rs_start);
1653 ASSERT3U(rc->rc_offset, <, physical_rs.rs_end);
1655 * It would be nice to assert that rs_end is equal
1656 * to rc_offset + rc_size but there might be an
1657 * optional I/O at the end that is not accounted in
1660 if (physical_rs.rs_end > rc->rc_offset + rc->rc_size) {
1661 ASSERT3U(physical_rs.rs_end, ==, rc->rc_offset +
1662 rc->rc_size + (1 << tvd->vdev_ashift));
1664 ASSERT3U(physical_rs.rs_end, ==, rc->rc_offset + rc->rc_size);
1670 * Start an IO operation on a RAIDZ VDev
1673 * - For write operations:
1674 * 1. Generate the parity data
1675 * 2. Create child zio write operations to each column's vdev, for both
1677 * 3. If the column skips any sectors for padding, create optional dummy
1678 * write zio children for those areas to improve aggregation continuity.
1679 * - For read operations:
1680 * 1. Create child zio read operations to each data column's vdev to read
1681 * the range of data required for zio.
1682 * 2. If this is a scrub or resilver operation, or if any of the data
1683 * vdevs have had errors, then create zio read operations to the parity
1684 * columns' VDevs as well.
1687 vdev_raidz_io_start(zio_t *zio)
1689 vdev_t *vd = zio->io_vd;
1690 vdev_t *tvd = vd->vdev_top;
1696 rm = vdev_raidz_map_alloc(zio, tvd->vdev_ashift, vd->vdev_children,
1699 ASSERT3U(rm->rm_asize, ==, vdev_psize_to_asize(vd, zio->io_size));
1701 if (zio->io_type == ZIO_TYPE_WRITE) {
1702 vdev_raidz_generate_parity(rm);
1704 for (c = 0; c < rm->rm_cols; c++) {
1705 rc = &rm->rm_col[c];
1706 cvd = vd->vdev_child[rc->rc_devidx];
1709 * Verify physical to logical translation.
1711 vdev_raidz_io_verify(zio, rm, c);
1713 zio_nowait(zio_vdev_child_io(zio, NULL, cvd,
1714 rc->rc_offset, rc->rc_abd, rc->rc_size,
1715 zio->io_type, zio->io_priority, 0,
1716 vdev_raidz_child_done, rc));
1720 * Generate optional I/Os for any skipped sectors to improve
1721 * aggregation contiguity.
1723 for (c = rm->rm_skipstart, i = 0; i < rm->rm_nskip; c++, i++) {
1724 ASSERT(c <= rm->rm_scols);
1725 if (c == rm->rm_scols)
1727 rc = &rm->rm_col[c];
1728 cvd = vd->vdev_child[rc->rc_devidx];
1729 zio_nowait(zio_vdev_child_io(zio, NULL, cvd,
1730 rc->rc_offset + rc->rc_size, NULL,
1731 1 << tvd->vdev_ashift,
1732 zio->io_type, zio->io_priority,
1733 ZIO_FLAG_NODATA | ZIO_FLAG_OPTIONAL, NULL, NULL));
1740 ASSERT(zio->io_type == ZIO_TYPE_READ);
1743 * Iterate over the columns in reverse order so that we hit the parity
1744 * last -- any errors along the way will force us to read the parity.
1746 for (c = rm->rm_cols - 1; c >= 0; c--) {
1747 rc = &rm->rm_col[c];
1748 cvd = vd->vdev_child[rc->rc_devidx];
1749 if (!vdev_readable(cvd)) {
1750 if (c >= rm->rm_firstdatacol)
1751 rm->rm_missingdata++;
1753 rm->rm_missingparity++;
1754 rc->rc_error = SET_ERROR(ENXIO);
1755 rc->rc_tried = 1; /* don't even try */
1759 if (vdev_dtl_contains(cvd, DTL_MISSING, zio->io_txg, 1)) {
1760 if (c >= rm->rm_firstdatacol)
1761 rm->rm_missingdata++;
1763 rm->rm_missingparity++;
1764 rc->rc_error = SET_ERROR(ESTALE);
1768 if (c >= rm->rm_firstdatacol || rm->rm_missingdata > 0 ||
1769 (zio->io_flags & (ZIO_FLAG_SCRUB | ZIO_FLAG_RESILVER))) {
1770 zio_nowait(zio_vdev_child_io(zio, NULL, cvd,
1771 rc->rc_offset, rc->rc_abd, rc->rc_size,
1772 zio->io_type, zio->io_priority, 0,
1773 vdev_raidz_child_done, rc));
1782 * Report a checksum error for a child of a RAID-Z device.
1785 raidz_checksum_error(zio_t *zio, raidz_col_t *rc, abd_t *bad_data)
1787 vdev_t *vd = zio->io_vd->vdev_child[rc->rc_devidx];
1789 if (!(zio->io_flags & ZIO_FLAG_SPECULATIVE)) {
1790 zio_bad_cksum_t zbc;
1791 raidz_map_t *rm = zio->io_vsd;
1793 mutex_enter(&vd->vdev_stat_lock);
1794 vd->vdev_stat.vs_checksum_errors++;
1795 mutex_exit(&vd->vdev_stat_lock);
1797 zbc.zbc_has_cksum = 0;
1798 zbc.zbc_injected = rm->rm_ecksuminjected;
1800 (void) zfs_ereport_post_checksum(zio->io_spa, vd,
1801 &zio->io_bookmark, zio, rc->rc_offset, rc->rc_size,
1802 rc->rc_abd, bad_data, &zbc);
1807 * We keep track of whether or not there were any injected errors, so that
1808 * any ereports we generate can note it.
1811 raidz_checksum_verify(zio_t *zio)
1813 zio_bad_cksum_t zbc;
1814 raidz_map_t *rm = zio->io_vsd;
1816 bzero(&zbc, sizeof (zio_bad_cksum_t));
1818 int ret = zio_checksum_error(zio, &zbc);
1819 if (ret != 0 && zbc.zbc_injected != 0)
1820 rm->rm_ecksuminjected = 1;
1826 * Generate the parity from the data columns. If we tried and were able to
1827 * read the parity without error, verify that the generated parity matches the
1828 * data we read. If it doesn't, we fire off a checksum error. Return the
1829 * number such failures.
1832 raidz_parity_verify(zio_t *zio, raidz_map_t *rm)
1834 abd_t *orig[VDEV_RAIDZ_MAXPARITY];
1838 blkptr_t *bp = zio->io_bp;
1839 enum zio_checksum checksum = (bp == NULL ? zio->io_prop.zp_checksum :
1840 (BP_IS_GANG(bp) ? ZIO_CHECKSUM_GANG_HEADER : BP_GET_CHECKSUM(bp)));
1842 if (checksum == ZIO_CHECKSUM_NOPARITY)
1845 for (c = 0; c < rm->rm_firstdatacol; c++) {
1846 rc = &rm->rm_col[c];
1847 if (!rc->rc_tried || rc->rc_error != 0)
1850 orig[c] = abd_alloc_sametype(rc->rc_abd, rc->rc_size);
1851 abd_copy(orig[c], rc->rc_abd, rc->rc_size);
1854 vdev_raidz_generate_parity(rm);
1856 for (c = 0; c < rm->rm_firstdatacol; c++) {
1857 rc = &rm->rm_col[c];
1858 if (!rc->rc_tried || rc->rc_error != 0)
1860 if (abd_cmp(orig[c], rc->rc_abd) != 0) {
1861 raidz_checksum_error(zio, rc, orig[c]);
1862 rc->rc_error = SET_ERROR(ECKSUM);
1872 vdev_raidz_worst_error(raidz_map_t *rm)
1876 for (int c = 0; c < rm->rm_cols; c++)
1877 error = zio_worst_error(error, rm->rm_col[c].rc_error);
1883 * Iterate over all combinations of bad data and attempt a reconstruction.
1884 * Note that the algorithm below is non-optimal because it doesn't take into
1885 * account how reconstruction is actually performed. For example, with
1886 * triple-parity RAID-Z the reconstruction procedure is the same if column 4
1887 * is targeted as invalid as if columns 1 and 4 are targeted since in both
1888 * cases we'd only use parity information in column 0.
1891 vdev_raidz_combrec(zio_t *zio, int total_errors, int data_errors)
1893 raidz_map_t *rm = zio->io_vsd;
1895 abd_t *orig[VDEV_RAIDZ_MAXPARITY];
1896 int tstore[VDEV_RAIDZ_MAXPARITY + 2];
1897 int *tgts = &tstore[1];
1898 int curr, next, i, c, n;
1901 ASSERT(total_errors < rm->rm_firstdatacol);
1904 * This simplifies one edge condition.
1908 for (n = 1; n <= rm->rm_firstdatacol - total_errors; n++) {
1910 * Initialize the targets array by finding the first n columns
1911 * that contain no error.
1913 * If there were no data errors, we need to ensure that we're
1914 * always explicitly attempting to reconstruct at least one
1915 * data column. To do this, we simply push the highest target
1916 * up into the data columns.
1918 for (c = 0, i = 0; i < n; i++) {
1919 if (i == n - 1 && data_errors == 0 &&
1920 c < rm->rm_firstdatacol) {
1921 c = rm->rm_firstdatacol;
1924 while (rm->rm_col[c].rc_error != 0) {
1926 ASSERT3S(c, <, rm->rm_cols);
1933 * Setting tgts[n] simplifies the other edge condition.
1935 tgts[n] = rm->rm_cols;
1938 * These buffers were allocated in previous iterations.
1940 for (i = 0; i < n - 1; i++) {
1941 ASSERT(orig[i] != NULL);
1944 orig[n - 1] = abd_alloc_sametype(rm->rm_col[0].rc_abd,
1945 rm->rm_col[0].rc_size);
1955 * Save off the original data that we're going to
1956 * attempt to reconstruct.
1958 for (i = 0; i < n; i++) {
1959 ASSERT(orig[i] != NULL);
1962 ASSERT3S(c, <, rm->rm_cols);
1963 rc = &rm->rm_col[c];
1964 abd_copy(orig[i], rc->rc_abd, rc->rc_size);
1968 * Attempt a reconstruction and exit the outer loop on
1971 code = vdev_raidz_reconstruct(rm, tgts, n);
1972 if (raidz_checksum_verify(zio) == 0) {
1974 for (i = 0; i < n; i++) {
1976 rc = &rm->rm_col[c];
1977 ASSERT(rc->rc_error == 0);
1979 raidz_checksum_error(zio, rc,
1981 rc->rc_error = SET_ERROR(ECKSUM);
1989 * Restore the original data.
1991 for (i = 0; i < n; i++) {
1993 rc = &rm->rm_col[c];
1994 abd_copy(rc->rc_abd, orig[i], rc->rc_size);
1999 * Find the next valid column after the curr
2002 for (next = tgts[curr] + 1;
2003 next < rm->rm_cols &&
2004 rm->rm_col[next].rc_error != 0; next++)
2007 ASSERT(next <= tgts[curr + 1]);
2010 * If that spot is available, we're done here.
2012 if (next != tgts[curr + 1])
2016 * Otherwise, find the next valid column after
2017 * the previous position.
2019 for (c = tgts[curr - 1] + 1;
2020 rm->rm_col[c].rc_error != 0; c++)
2026 } while (curr != n);
2031 for (i = 0; i < n; i++)
2038 * Complete an IO operation on a RAIDZ VDev
2041 * - For write operations:
2042 * 1. Check for errors on the child IOs.
2043 * 2. Return, setting an error code if too few child VDevs were written
2044 * to reconstruct the data later. Note that partial writes are
2045 * considered successful if they can be reconstructed at all.
2046 * - For read operations:
2047 * 1. Check for errors on the child IOs.
2048 * 2. If data errors occurred:
2049 * a. Try to reassemble the data from the parity available.
2050 * b. If we haven't yet read the parity drives, read them now.
2051 * c. If all parity drives have been read but the data still doesn't
2052 * reassemble with a correct checksum, then try combinatorial
2054 * d. If that doesn't work, return an error.
2055 * 3. If there were unexpected errors or this is a resilver operation,
2056 * rewrite the vdevs that had errors.
2059 vdev_raidz_io_done(zio_t *zio)
2061 vdev_t *vd = zio->io_vd;
2063 raidz_map_t *rm = zio->io_vsd;
2064 raidz_col_t *rc = NULL;
2065 int unexpected_errors = 0;
2066 int parity_errors = 0;
2067 int parity_untried = 0;
2068 int data_errors = 0;
2069 int total_errors = 0;
2071 int tgts[VDEV_RAIDZ_MAXPARITY];
2074 ASSERT(zio->io_bp != NULL); /* XXX need to add code to enforce this */
2076 ASSERT(rm->rm_missingparity <= rm->rm_firstdatacol);
2077 ASSERT(rm->rm_missingdata <= rm->rm_cols - rm->rm_firstdatacol);
2079 for (c = 0; c < rm->rm_cols; c++) {
2080 rc = &rm->rm_col[c];
2083 ASSERT(rc->rc_error != ECKSUM); /* child has no bp */
2085 if (c < rm->rm_firstdatacol)
2090 if (!rc->rc_skipped)
2091 unexpected_errors++;
2094 } else if (c < rm->rm_firstdatacol && !rc->rc_tried) {
2099 if (zio->io_type == ZIO_TYPE_WRITE) {
2101 * XXX -- for now, treat partial writes as a success.
2102 * (If we couldn't write enough columns to reconstruct
2103 * the data, the I/O failed. Otherwise, good enough.)
2105 * Now that we support write reallocation, it would be better
2106 * to treat partial failure as real failure unless there are
2107 * no non-degraded top-level vdevs left, and not update DTLs
2108 * if we intend to reallocate.
2111 if (total_errors > rm->rm_firstdatacol)
2112 zio->io_error = vdev_raidz_worst_error(rm);
2117 ASSERT(zio->io_type == ZIO_TYPE_READ);
2119 * There are three potential phases for a read:
2120 * 1. produce valid data from the columns read
2121 * 2. read all disks and try again
2122 * 3. perform combinatorial reconstruction
2124 * Each phase is progressively both more expensive and less likely to
2125 * occur. If we encounter more errors than we can repair or all phases
2126 * fail, we have no choice but to return an error.
2130 * If the number of errors we saw was correctable -- less than or equal
2131 * to the number of parity disks read -- attempt to produce data that
2132 * has a valid checksum. Naturally, this case applies in the absence of
2135 if (total_errors <= rm->rm_firstdatacol - parity_untried) {
2136 if (data_errors == 0) {
2137 if (raidz_checksum_verify(zio) == 0) {
2139 * If we read parity information (unnecessarily
2140 * as it happens since no reconstruction was
2141 * needed) regenerate and verify the parity.
2142 * We also regenerate parity when resilvering
2143 * so we can write it out to the failed device
2146 if (parity_errors + parity_untried <
2147 rm->rm_firstdatacol ||
2148 (zio->io_flags & ZIO_FLAG_RESILVER)) {
2149 n = raidz_parity_verify(zio, rm);
2150 unexpected_errors += n;
2151 ASSERT(parity_errors + n <=
2152 rm->rm_firstdatacol);
2158 * We either attempt to read all the parity columns or
2159 * none of them. If we didn't try to read parity, we
2160 * wouldn't be here in the correctable case. There must
2161 * also have been fewer parity errors than parity
2162 * columns or, again, we wouldn't be in this code path.
2164 ASSERT(parity_untried == 0);
2165 ASSERT(parity_errors < rm->rm_firstdatacol);
2168 * Identify the data columns that reported an error.
2171 for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
2172 rc = &rm->rm_col[c];
2173 if (rc->rc_error != 0) {
2174 ASSERT(n < VDEV_RAIDZ_MAXPARITY);
2179 ASSERT(rm->rm_firstdatacol >= n);
2181 code = vdev_raidz_reconstruct(rm, tgts, n);
2183 if (raidz_checksum_verify(zio) == 0) {
2185 * If we read more parity disks than were used
2186 * for reconstruction, confirm that the other
2187 * parity disks produced correct data. This
2188 * routine is suboptimal in that it regenerates
2189 * the parity that we already used in addition
2190 * to the parity that we're attempting to
2191 * verify, but this should be a relatively
2192 * uncommon case, and can be optimized if it
2193 * becomes a problem. Note that we regenerate
2194 * parity when resilvering so we can write it
2195 * out to failed devices later.
2197 if (parity_errors < rm->rm_firstdatacol - n ||
2198 (zio->io_flags & ZIO_FLAG_RESILVER)) {
2199 n = raidz_parity_verify(zio, rm);
2200 unexpected_errors += n;
2201 ASSERT(parity_errors + n <=
2202 rm->rm_firstdatacol);
2211 * This isn't a typical situation -- either we got a read error or
2212 * a child silently returned bad data. Read every block so we can
2213 * try again with as much data and parity as we can track down. If
2214 * we've already been through once before, all children will be marked
2215 * as tried so we'll proceed to combinatorial reconstruction.
2217 unexpected_errors = 1;
2218 rm->rm_missingdata = 0;
2219 rm->rm_missingparity = 0;
2221 for (c = 0; c < rm->rm_cols; c++) {
2222 if (rm->rm_col[c].rc_tried)
2225 zio_vdev_io_redone(zio);
2227 rc = &rm->rm_col[c];
2230 zio_nowait(zio_vdev_child_io(zio, NULL,
2231 vd->vdev_child[rc->rc_devidx],
2232 rc->rc_offset, rc->rc_abd, rc->rc_size,
2233 zio->io_type, zio->io_priority, 0,
2234 vdev_raidz_child_done, rc));
2235 } while (++c < rm->rm_cols);
2241 * At this point we've attempted to reconstruct the data given the
2242 * errors we detected, and we've attempted to read all columns. There
2243 * must, therefore, be one or more additional problems -- silent errors
2244 * resulting in invalid data rather than explicit I/O errors resulting
2245 * in absent data. We check if there is enough additional data to
2246 * possibly reconstruct the data and then perform combinatorial
2247 * reconstruction over all possible combinations. If that fails,
2250 if (total_errors > rm->rm_firstdatacol) {
2251 zio->io_error = vdev_raidz_worst_error(rm);
2253 } else if (total_errors < rm->rm_firstdatacol &&
2254 (code = vdev_raidz_combrec(zio, total_errors, data_errors)) != 0) {
2256 * If we didn't use all the available parity for the
2257 * combinatorial reconstruction, verify that the remaining
2258 * parity is correct.
2260 if (code != (1 << rm->rm_firstdatacol) - 1)
2261 (void) raidz_parity_verify(zio, rm);
2264 * We're here because either:
2266 * total_errors == rm_first_datacol, or
2267 * vdev_raidz_combrec() failed
2269 * In either case, there is enough bad data to prevent
2272 * Start checksum ereports for all children which haven't
2273 * failed, and the IO wasn't speculative.
2275 zio->io_error = SET_ERROR(ECKSUM);
2277 if (!(zio->io_flags & ZIO_FLAG_SPECULATIVE)) {
2278 for (c = 0; c < rm->rm_cols; c++) {
2280 rc = &rm->rm_col[c];
2281 cvd = vd->vdev_child[rc->rc_devidx];
2282 if (rc->rc_error == 0) {
2283 zio_bad_cksum_t zbc;
2284 zbc.zbc_has_cksum = 0;
2286 rm->rm_ecksuminjected;
2288 mutex_enter(&cvd->vdev_stat_lock);
2289 cvd->vdev_stat.vs_checksum_errors++;
2290 mutex_exit(&cvd->vdev_stat_lock);
2292 zfs_ereport_start_checksum(
2294 &zio->io_bookmark, zio,
2295 rc->rc_offset, rc->rc_size,
2296 (void *)(uintptr_t)c, &zbc);
2303 zio_checksum_verified(zio);
2305 if (zio->io_error == 0 && spa_writeable(zio->io_spa) &&
2306 (unexpected_errors || (zio->io_flags & ZIO_FLAG_RESILVER))) {
2308 * Use the good data we have in hand to repair damaged children.
2310 for (c = 0; c < rm->rm_cols; c++) {
2311 rc = &rm->rm_col[c];
2312 cvd = vd->vdev_child[rc->rc_devidx];
2314 if (rc->rc_error == 0)
2317 zio_nowait(zio_vdev_child_io(zio, NULL, cvd,
2318 rc->rc_offset, rc->rc_abd, rc->rc_size,
2319 ZIO_TYPE_WRITE, ZIO_PRIORITY_ASYNC_WRITE,
2320 ZIO_FLAG_IO_REPAIR | (unexpected_errors ?
2321 ZIO_FLAG_SELF_HEAL : 0), NULL, NULL));
2327 vdev_raidz_state_change(vdev_t *vd, int faulted, int degraded)
2329 if (faulted > vd->vdev_nparity)
2330 vdev_set_state(vd, B_FALSE, VDEV_STATE_CANT_OPEN,
2331 VDEV_AUX_NO_REPLICAS);
2332 else if (degraded + faulted != 0)
2333 vdev_set_state(vd, B_FALSE, VDEV_STATE_DEGRADED, VDEV_AUX_NONE);
2335 vdev_set_state(vd, B_FALSE, VDEV_STATE_HEALTHY, VDEV_AUX_NONE);
2339 * Determine if any portion of the provided block resides on a child vdev
2340 * with a dirty DTL and therefore needs to be resilvered. The function
2341 * assumes that at least one DTL is dirty which implies that full stripe
2342 * width blocks must be resilvered.
2345 vdev_raidz_need_resilver(vdev_t *vd, uint64_t offset, size_t psize)
2347 uint64_t dcols = vd->vdev_children;
2348 uint64_t nparity = vd->vdev_nparity;
2349 uint64_t ashift = vd->vdev_top->vdev_ashift;
2350 /* The starting RAIDZ (parent) vdev sector of the block. */
2351 uint64_t b = offset >> ashift;
2352 /* The zio's size in units of the vdev's minimum sector size. */
2353 uint64_t s = ((psize - 1) >> ashift) + 1;
2354 /* The first column for this stripe. */
2355 uint64_t f = b % dcols;
2357 if (s + nparity >= dcols)
2360 for (uint64_t c = 0; c < s + nparity; c++) {
2361 uint64_t devidx = (f + c) % dcols;
2362 vdev_t *cvd = vd->vdev_child[devidx];
2365 * dsl_scan_need_resilver() already checked vd with
2366 * vdev_dtl_contains(). So here just check cvd with
2367 * vdev_dtl_empty(), cheaper and a good approximation.
2369 if (!vdev_dtl_empty(cvd, DTL_PARTIAL))
2377 vdev_raidz_xlate(vdev_t *cvd, const range_seg64_t *in, range_seg64_t *res)
2379 vdev_t *raidvd = cvd->vdev_parent;
2380 ASSERT(raidvd->vdev_ops == &vdev_raidz_ops);
2382 uint64_t width = raidvd->vdev_children;
2383 uint64_t tgt_col = cvd->vdev_id;
2384 uint64_t ashift = raidvd->vdev_top->vdev_ashift;
2386 /* make sure the offsets are block-aligned */
2387 ASSERT0(in->rs_start % (1 << ashift));
2388 ASSERT0(in->rs_end % (1 << ashift));
2389 uint64_t b_start = in->rs_start >> ashift;
2390 uint64_t b_end = in->rs_end >> ashift;
2392 uint64_t start_row = 0;
2393 if (b_start > tgt_col) /* avoid underflow */
2394 start_row = ((b_start - tgt_col - 1) / width) + 1;
2396 uint64_t end_row = 0;
2397 if (b_end > tgt_col)
2398 end_row = ((b_end - tgt_col - 1) / width) + 1;
2400 res->rs_start = start_row << ashift;
2401 res->rs_end = end_row << ashift;
2403 ASSERT3U(res->rs_start, <=, in->rs_start);
2404 ASSERT3U(res->rs_end - res->rs_start, <=, in->rs_end - in->rs_start);
2407 vdev_ops_t vdev_raidz_ops = {
2408 .vdev_op_open = vdev_raidz_open,
2409 .vdev_op_close = vdev_raidz_close,
2410 .vdev_op_asize = vdev_raidz_asize,
2411 .vdev_op_io_start = vdev_raidz_io_start,
2412 .vdev_op_io_done = vdev_raidz_io_done,
2413 .vdev_op_state_change = vdev_raidz_state_change,
2414 .vdev_op_need_resilver = vdev_raidz_need_resilver,
2415 .vdev_op_hold = NULL,
2416 .vdev_op_rele = NULL,
2417 .vdev_op_remap = NULL,
2418 .vdev_op_xlate = vdev_raidz_xlate,
2419 .vdev_op_type = VDEV_TYPE_RAIDZ, /* name of this vdev type */
2420 .vdev_op_leaf = B_FALSE /* not a leaf vdev */