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, 2014 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 * Virtual device vector for RAID-Z.
42 * This vdev supports single, double, and triple parity. For single parity,
43 * we use a simple XOR of all the data columns. For double or triple parity,
44 * we use a special case of Reed-Solomon coding. This extends the
45 * technique described in "The mathematics of RAID-6" by H. Peter Anvin by
46 * drawing on the system described in "A Tutorial on Reed-Solomon Coding for
47 * Fault-Tolerance in RAID-like Systems" by James S. Plank on which the
48 * former is also based. The latter is designed to provide higher performance
51 * Note that the Plank paper claimed to support arbitrary N+M, but was then
52 * amended six years later identifying a critical flaw that invalidates its
53 * claims. Nevertheless, the technique can be adapted to work for up to
54 * triple parity. For additional parity, the amendment "Note: Correction to
55 * the 1997 Tutorial on Reed-Solomon Coding" by James S. Plank and Ying Ding
56 * is viable, but the additional complexity means that write performance will
59 * All of the methods above operate on a Galois field, defined over the
60 * integers mod 2^N. In our case we choose N=8 for GF(8) so that all elements
61 * can be expressed with a single byte. Briefly, the operations on the
62 * field are defined as follows:
64 * o addition (+) is represented by a bitwise XOR
65 * o subtraction (-) is therefore identical to addition: A + B = A - B
66 * o multiplication of A by 2 is defined by the following bitwise expression:
71 * (A * 2)_4 = A_3 + A_7
72 * (A * 2)_3 = A_2 + A_7
73 * (A * 2)_2 = A_1 + A_7
77 * In C, multiplying by 2 is therefore ((a << 1) ^ ((a & 0x80) ? 0x1d : 0)).
78 * As an aside, this multiplication is derived from the error correcting
79 * primitive polynomial x^8 + x^4 + x^3 + x^2 + 1.
81 * Observe that any number in the field (except for 0) can be expressed as a
82 * power of 2 -- a generator for the field. We store a table of the powers of
83 * 2 and logs base 2 for quick look ups, and exploit the fact that A * B can
84 * be rewritten as 2^(log_2(A) + log_2(B)) (where '+' is normal addition rather
85 * than field addition). The inverse of a field element A (A^-1) is therefore
86 * A ^ (255 - 1) = A^254.
88 * The up-to-three parity columns, P, Q, R over several data columns,
89 * D_0, ... D_n-1, can be expressed by field operations:
91 * P = D_0 + D_1 + ... + D_n-2 + D_n-1
92 * Q = 2^n-1 * D_0 + 2^n-2 * D_1 + ... + 2^1 * D_n-2 + 2^0 * D_n-1
93 * = ((...((D_0) * 2 + D_1) * 2 + ...) * 2 + D_n-2) * 2 + D_n-1
94 * R = 4^n-1 * D_0 + 4^n-2 * D_1 + ... + 4^1 * D_n-2 + 4^0 * D_n-1
95 * = ((...((D_0) * 4 + D_1) * 4 + ...) * 4 + D_n-2) * 4 + D_n-1
97 * We chose 1, 2, and 4 as our generators because 1 corresponds to the trival
98 * XOR operation, and 2 and 4 can be computed quickly and generate linearly-
99 * independent coefficients. (There are no additional coefficients that have
100 * this property which is why the uncorrected Plank method breaks down.)
102 * See the reconstruction code below for how P, Q and R can used individually
103 * or in concert to recover missing data columns.
106 #define VDEV_RAIDZ_P 0
107 #define VDEV_RAIDZ_Q 1
108 #define VDEV_RAIDZ_R 2
110 #define VDEV_RAIDZ_MUL_2(x) (((x) << 1) ^ (((x) & 0x80) ? 0x1d : 0))
111 #define VDEV_RAIDZ_MUL_4(x) (VDEV_RAIDZ_MUL_2(VDEV_RAIDZ_MUL_2(x)))
114 * We provide a mechanism to perform the field multiplication operation on a
115 * 64-bit value all at once rather than a byte at a time. This works by
116 * creating a mask from the top bit in each byte and using that to
117 * conditionally apply the XOR of 0x1d.
119 #define VDEV_RAIDZ_64MUL_2(x, mask) \
121 (mask) = (x) & 0x8080808080808080ULL; \
122 (mask) = ((mask) << 1) - ((mask) >> 7); \
123 (x) = (((x) << 1) & 0xfefefefefefefefeULL) ^ \
124 ((mask) & 0x1d1d1d1d1d1d1d1dULL); \
127 #define VDEV_RAIDZ_64MUL_4(x, mask) \
129 VDEV_RAIDZ_64MUL_2((x), mask); \
130 VDEV_RAIDZ_64MUL_2((x), mask); \
134 vdev_raidz_map_free(raidz_map_t
*rm
)
139 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++) {
140 abd_free(rm
->rm_col
[c
].rc_abd
);
142 if (rm
->rm_col
[c
].rc_gdata
!= NULL
)
143 zio_buf_free(rm
->rm_col
[c
].rc_gdata
,
144 rm
->rm_col
[c
].rc_size
);
148 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
149 abd_put(rm
->rm_col
[c
].rc_abd
);
150 size
+= rm
->rm_col
[c
].rc_size
;
153 if (rm
->rm_abd_copy
!= NULL
)
154 abd_free(rm
->rm_abd_copy
);
156 kmem_free(rm
, offsetof(raidz_map_t
, rm_col
[rm
->rm_scols
]));
160 vdev_raidz_map_free_vsd(zio_t
*zio
)
162 raidz_map_t
*rm
= zio
->io_vsd
;
164 ASSERT0(rm
->rm_freed
);
167 if (rm
->rm_reports
== 0)
168 vdev_raidz_map_free(rm
);
173 vdev_raidz_cksum_free(void *arg
, size_t ignored
)
175 raidz_map_t
*rm
= arg
;
177 ASSERT3U(rm
->rm_reports
, >, 0);
179 if (--rm
->rm_reports
== 0 && rm
->rm_freed
!= 0)
180 vdev_raidz_map_free(rm
);
184 vdev_raidz_cksum_finish(zio_cksum_report_t
*zcr
, const void *good_data
)
186 raidz_map_t
*rm
= zcr
->zcr_cbdata
;
187 size_t c
= zcr
->zcr_cbinfo
;
190 const char *good
= NULL
;
193 if (good_data
== NULL
) {
194 zfs_ereport_finish_checksum(zcr
, NULL
, NULL
, B_FALSE
);
198 if (c
< rm
->rm_firstdatacol
) {
200 * The first time through, calculate the parity blocks for
201 * the good data (this relies on the fact that the good
202 * data never changes for a given logical ZIO)
204 if (rm
->rm_col
[0].rc_gdata
== NULL
) {
205 abd_t
*bad_parity
[VDEV_RAIDZ_MAXPARITY
];
210 * Set up the rm_col[]s to generate the parity for
211 * good_data, first saving the parity bufs and
212 * replacing them with buffers to hold the result.
214 for (x
= 0; x
< rm
->rm_firstdatacol
; x
++) {
215 bad_parity
[x
] = rm
->rm_col
[x
].rc_abd
;
216 rm
->rm_col
[x
].rc_gdata
=
217 zio_buf_alloc(rm
->rm_col
[x
].rc_size
);
218 rm
->rm_col
[x
].rc_abd
=
219 abd_get_from_buf(rm
->rm_col
[x
].rc_gdata
,
220 rm
->rm_col
[x
].rc_size
);
223 /* fill in the data columns from good_data */
224 buf
= (char *)good_data
;
225 for (; x
< rm
->rm_cols
; x
++) {
226 abd_put(rm
->rm_col
[x
].rc_abd
);
227 rm
->rm_col
[x
].rc_abd
= abd_get_from_buf(buf
,
228 rm
->rm_col
[x
].rc_size
);
229 buf
+= rm
->rm_col
[x
].rc_size
;
233 * Construct the parity from the good data.
235 vdev_raidz_generate_parity(rm
);
237 /* restore everything back to its original state */
238 for (x
= 0; x
< rm
->rm_firstdatacol
; x
++) {
239 abd_put(rm
->rm_col
[x
].rc_abd
);
240 rm
->rm_col
[x
].rc_abd
= bad_parity
[x
];
244 for (x
= rm
->rm_firstdatacol
; x
< rm
->rm_cols
; x
++) {
245 abd_put(rm
->rm_col
[x
].rc_abd
);
246 rm
->rm_col
[x
].rc_abd
= abd_get_offset(
247 rm
->rm_abd_copy
, offset
);
248 offset
+= rm
->rm_col
[x
].rc_size
;
252 ASSERT3P(rm
->rm_col
[c
].rc_gdata
, !=, NULL
);
253 good
= rm
->rm_col
[c
].rc_gdata
;
255 /* adjust good_data to point at the start of our column */
258 for (x
= rm
->rm_firstdatacol
; x
< c
; x
++)
259 good
+= rm
->rm_col
[x
].rc_size
;
262 bad
= abd_borrow_buf_copy(rm
->rm_col
[c
].rc_abd
, rm
->rm_col
[c
].rc_size
);
263 /* we drop the ereport if it ends up that the data was good */
264 zfs_ereport_finish_checksum(zcr
, good
, bad
, B_TRUE
);
265 abd_return_buf(rm
->rm_col
[c
].rc_abd
, bad
, rm
->rm_col
[c
].rc_size
);
269 * Invoked indirectly by zfs_ereport_start_checksum(), called
270 * below when our read operation fails completely. The main point
271 * is to keep a copy of everything we read from disk, so that at
272 * vdev_raidz_cksum_finish() time we can compare it with the good data.
275 vdev_raidz_cksum_report(zio_t
*zio
, zio_cksum_report_t
*zcr
, void *arg
)
277 size_t c
= (size_t)(uintptr_t)arg
;
280 raidz_map_t
*rm
= zio
->io_vsd
;
283 /* set up the report and bump the refcount */
284 zcr
->zcr_cbdata
= rm
;
286 zcr
->zcr_finish
= vdev_raidz_cksum_finish
;
287 zcr
->zcr_free
= vdev_raidz_cksum_free
;
290 ASSERT3U(rm
->rm_reports
, >, 0);
292 if (rm
->rm_abd_copy
!= NULL
)
296 * It's the first time we're called for this raidz_map_t, so we need
297 * to copy the data aside; there's no guarantee that our zio's buffer
298 * won't be re-used for something else.
300 * Our parity data is already in separate buffers, so there's no need
305 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++)
306 size
+= rm
->rm_col
[c
].rc_size
;
309 abd_alloc_sametype(rm
->rm_col
[rm
->rm_firstdatacol
].rc_abd
, size
);
311 for (offset
= 0, c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
312 raidz_col_t
*col
= &rm
->rm_col
[c
];
313 abd_t
*tmp
= abd_get_offset(rm
->rm_abd_copy
, offset
);
315 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 vdev_raidz_map_free_vsd
,
326 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 unit_shift
, uint64_t dcols
,
341 /* The starting RAIDZ (parent) vdev sector of the block. */
342 uint64_t b
= zio
->io_offset
>> unit_shift
;
343 /* The zio's size in units of the vdev's minimum sector size. */
344 uint64_t s
= zio
->io_size
>> unit_shift
;
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
) << unit_shift
;
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 << unit_shift
;
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) << unit_shift
;
422 rm
->rm_col
[c
].rc_size
= q
<< unit_shift
;
424 asize
+= rm
->rm_col
[c
].rc_size
;
427 ASSERT3U(asize
, ==, tot
<< unit_shift
);
428 rm
->rm_asize
= roundup(asize
, (nparity
+ 1) << unit_shift
);
429 rm
->rm_nskip
= roundup(tot
, nparity
+ 1) - tot
;
430 ASSERT3U(rm
->rm_asize
- asize
, ==, rm
->rm_nskip
<< unit_shift
);
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_TRUE
);
437 rm
->rm_col
[c
].rc_abd
= abd_get_offset(zio
->io_abd
, 0);
438 off
= rm
->rm_col
[c
].rc_size
;
440 for (c
= c
+ 1; c
< acols
; c
++) {
441 rm
->rm_col
[c
].rc_abd
= abd_get_offset(zio
->io_abd
, off
);
442 off
+= rm
->rm_col
[c
].rc_size
;
446 * If all data stored spans all columns, there's a danger that parity
447 * will always be on the same device and, since parity isn't read
448 * during normal operation, that that device's I/O bandwidth won't be
449 * used effectively. We therefore switch the parity every 1MB.
451 * ... at least that was, ostensibly, the theory. As a practical
452 * matter unless we juggle the parity between all devices evenly, we
453 * won't see any benefit. Further, occasional writes that aren't a
454 * multiple of the LCM of the number of children and the minimum
455 * stripe width are sufficient to avoid pessimal behavior.
456 * Unfortunately, this decision created an implicit on-disk format
457 * requirement that we need to support for all eternity, but only
458 * for single-parity RAID-Z.
460 * If we intend to skip a sector in the zeroth column for padding
461 * we must make sure to note this swap. We will never intend to
462 * skip the first column since at least one data and one parity
463 * column must appear in each row.
465 ASSERT(rm
->rm_cols
>= 2);
466 ASSERT(rm
->rm_col
[0].rc_size
== rm
->rm_col
[1].rc_size
);
468 if (rm
->rm_firstdatacol
== 1 && (zio
->io_offset
& (1ULL << 20))) {
469 devidx
= rm
->rm_col
[0].rc_devidx
;
470 o
= rm
->rm_col
[0].rc_offset
;
471 rm
->rm_col
[0].rc_devidx
= rm
->rm_col
[1].rc_devidx
;
472 rm
->rm_col
[0].rc_offset
= rm
->rm_col
[1].rc_offset
;
473 rm
->rm_col
[1].rc_devidx
= devidx
;
474 rm
->rm_col
[1].rc_offset
= o
;
476 if (rm
->rm_skipstart
== 0)
477 rm
->rm_skipstart
= 1;
481 zio
->io_vsd_ops
= &vdev_raidz_vsd_ops
;
483 /* init RAIDZ parity ops */
484 rm
->rm_ops
= vdev_raidz_math_get_ops();
496 vdev_raidz_p_func(void *buf
, size_t size
, void *private)
498 struct pqr_struct
*pqr
= private;
499 const uint64_t *src
= buf
;
500 int i
, cnt
= size
/ sizeof (src
[0]);
502 ASSERT(pqr
->p
&& !pqr
->q
&& !pqr
->r
);
504 for (i
= 0; i
< cnt
; i
++, src
++, pqr
->p
++)
511 vdev_raidz_pq_func(void *buf
, size_t size
, void *private)
513 struct pqr_struct
*pqr
= private;
514 const uint64_t *src
= buf
;
516 int i
, cnt
= size
/ sizeof (src
[0]);
518 ASSERT(pqr
->p
&& pqr
->q
&& !pqr
->r
);
520 for (i
= 0; i
< cnt
; i
++, src
++, pqr
->p
++, pqr
->q
++) {
522 VDEV_RAIDZ_64MUL_2(*pqr
->q
, mask
);
530 vdev_raidz_pqr_func(void *buf
, size_t size
, void *private)
532 struct pqr_struct
*pqr
= private;
533 const uint64_t *src
= buf
;
535 int i
, cnt
= size
/ sizeof (src
[0]);
537 ASSERT(pqr
->p
&& pqr
->q
&& pqr
->r
);
539 for (i
= 0; i
< cnt
; i
++, src
++, pqr
->p
++, pqr
->q
++, pqr
->r
++) {
541 VDEV_RAIDZ_64MUL_2(*pqr
->q
, mask
);
543 VDEV_RAIDZ_64MUL_4(*pqr
->r
, mask
);
551 vdev_raidz_generate_parity_p(raidz_map_t
*rm
)
557 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
558 src
= rm
->rm_col
[c
].rc_abd
;
559 p
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
561 if (c
== rm
->rm_firstdatacol
) {
562 abd_copy_to_buf(p
, src
, rm
->rm_col
[c
].rc_size
);
564 struct pqr_struct pqr
= { p
, NULL
, NULL
};
565 (void) abd_iterate_func(src
, 0, rm
->rm_col
[c
].rc_size
,
566 vdev_raidz_p_func
, &pqr
);
572 vdev_raidz_generate_parity_pq(raidz_map_t
*rm
)
574 uint64_t *p
, *q
, pcnt
, ccnt
, mask
, i
;
578 pcnt
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
/ sizeof (p
[0]);
579 ASSERT(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
==
580 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
);
582 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
583 src
= rm
->rm_col
[c
].rc_abd
;
584 p
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
585 q
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
587 ccnt
= rm
->rm_col
[c
].rc_size
/ sizeof (p
[0]);
589 if (c
== rm
->rm_firstdatacol
) {
590 abd_copy_to_buf(p
, src
, rm
->rm_col
[c
].rc_size
);
591 (void) memcpy(q
, p
, rm
->rm_col
[c
].rc_size
);
593 struct pqr_struct pqr
= { p
, q
, NULL
};
594 (void) abd_iterate_func(src
, 0, rm
->rm_col
[c
].rc_size
,
595 vdev_raidz_pq_func
, &pqr
);
598 if (c
== rm
->rm_firstdatacol
) {
599 for (i
= ccnt
; i
< pcnt
; i
++) {
606 * Treat short columns as though they are full of 0s.
607 * Note that there's therefore nothing needed for P.
609 for (i
= ccnt
; i
< pcnt
; i
++) {
610 VDEV_RAIDZ_64MUL_2(q
[i
], mask
);
617 vdev_raidz_generate_parity_pqr(raidz_map_t
*rm
)
619 uint64_t *p
, *q
, *r
, pcnt
, ccnt
, mask
, i
;
623 pcnt
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
/ sizeof (p
[0]);
624 ASSERT(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
==
625 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
);
626 ASSERT(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
==
627 rm
->rm_col
[VDEV_RAIDZ_R
].rc_size
);
629 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
630 src
= rm
->rm_col
[c
].rc_abd
;
631 p
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
632 q
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
633 r
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_R
].rc_abd
);
635 ccnt
= rm
->rm_col
[c
].rc_size
/ sizeof (p
[0]);
637 if (c
== rm
->rm_firstdatacol
) {
638 abd_copy_to_buf(p
, src
, rm
->rm_col
[c
].rc_size
);
639 (void) memcpy(q
, p
, rm
->rm_col
[c
].rc_size
);
640 (void) memcpy(r
, p
, rm
->rm_col
[c
].rc_size
);
642 struct pqr_struct pqr
= { p
, q
, r
};
643 (void) abd_iterate_func(src
, 0, rm
->rm_col
[c
].rc_size
,
644 vdev_raidz_pqr_func
, &pqr
);
647 if (c
== rm
->rm_firstdatacol
) {
648 for (i
= ccnt
; i
< pcnt
; i
++) {
655 * Treat short columns as though they are full of 0s.
656 * Note that there's therefore nothing needed for P.
658 for (i
= ccnt
; i
< pcnt
; i
++) {
659 VDEV_RAIDZ_64MUL_2(q
[i
], mask
);
660 VDEV_RAIDZ_64MUL_4(r
[i
], mask
);
667 * Generate RAID parity in the first virtual columns according to the number of
668 * parity columns available.
671 vdev_raidz_generate_parity(raidz_map_t
*rm
)
673 /* Generate using the new math implementation */
674 if (vdev_raidz_math_generate(rm
) != RAIDZ_ORIGINAL_IMPL
)
677 switch (rm
->rm_firstdatacol
) {
679 vdev_raidz_generate_parity_p(rm
);
682 vdev_raidz_generate_parity_pq(rm
);
685 vdev_raidz_generate_parity_pqr(rm
);
688 cmn_err(CE_PANIC
, "invalid RAID-Z configuration");
694 vdev_raidz_reconst_p_func(void *dbuf
, void *sbuf
, size_t size
, void *private)
696 uint64_t *dst
= dbuf
;
697 uint64_t *src
= sbuf
;
698 int cnt
= size
/ sizeof (src
[0]);
701 for (i
= 0; i
< cnt
; i
++) {
710 vdev_raidz_reconst_q_pre_func(void *dbuf
, void *sbuf
, size_t size
,
713 uint64_t *dst
= dbuf
;
714 uint64_t *src
= sbuf
;
716 int cnt
= size
/ sizeof (dst
[0]);
719 for (i
= 0; i
< cnt
; i
++, dst
++, src
++) {
720 VDEV_RAIDZ_64MUL_2(*dst
, mask
);
729 vdev_raidz_reconst_q_pre_tail_func(void *buf
, size_t size
, void *private)
733 int cnt
= size
/ sizeof (dst
[0]);
736 for (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]);
757 for (i
= 0; i
< cnt
; i
++, dst
++, rq
->q
++) {
762 for (j
= 0, b
= (uint8_t *)dst
; j
< 8; j
++, b
++) {
763 *b
= vdev_raidz_exp2(*b
, rq
->exp
);
770 struct reconst_pq_struct
{
780 vdev_raidz_reconst_pq_func(void *xbuf
, void *ybuf
, size_t size
, void *private)
782 struct reconst_pq_struct
*rpq
= private;
787 for (i
= 0; i
< size
;
788 i
++, rpq
->p
++, rpq
->q
++, rpq
->pxy
++, rpq
->qxy
++, xd
++, yd
++) {
789 *xd
= vdev_raidz_exp2(*rpq
->p
^ *rpq
->pxy
, rpq
->aexp
) ^
790 vdev_raidz_exp2(*rpq
->q
^ *rpq
->qxy
, rpq
->bexp
);
791 *yd
= *rpq
->p
^ *rpq
->pxy
^ *xd
;
798 vdev_raidz_reconst_pq_tail_func(void *xbuf
, size_t size
, void *private)
800 struct reconst_pq_struct
*rpq
= private;
804 for (i
= 0; i
< size
;
805 i
++, rpq
->p
++, rpq
->q
++, rpq
->pxy
++, rpq
->qxy
++, xd
++) {
806 /* same operation as vdev_raidz_reconst_pq_func() on xd */
807 *xd
= vdev_raidz_exp2(*rpq
->p
^ *rpq
->pxy
, rpq
->aexp
) ^
808 vdev_raidz_exp2(*rpq
->q
^ *rpq
->qxy
, rpq
->bexp
);
815 vdev_raidz_reconstruct_p(raidz_map_t
*rm
, int *tgts
, int ntgts
)
822 ASSERT(x
>= rm
->rm_firstdatacol
);
823 ASSERT(x
< rm
->rm_cols
);
825 ASSERT(rm
->rm_col
[x
].rc_size
<= rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
);
826 ASSERT(rm
->rm_col
[x
].rc_size
> 0);
828 src
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
;
829 dst
= rm
->rm_col
[x
].rc_abd
;
831 abd_copy_from_buf(dst
, abd_to_buf(src
), rm
->rm_col
[x
].rc_size
);
833 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
834 uint64_t size
= MIN(rm
->rm_col
[x
].rc_size
,
835 rm
->rm_col
[c
].rc_size
);
837 src
= rm
->rm_col
[c
].rc_abd
;
838 dst
= rm
->rm_col
[x
].rc_abd
;
843 (void) abd_iterate_func2(dst
, src
, 0, 0, size
,
844 vdev_raidz_reconst_p_func
, NULL
);
847 return (1 << VDEV_RAIDZ_P
);
851 vdev_raidz_reconstruct_q(raidz_map_t
*rm
, int *tgts
, int ntgts
)
856 struct reconst_q_struct rq
;
860 ASSERT(rm
->rm_col
[x
].rc_size
<= rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
);
862 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
863 uint64_t size
= (c
== x
) ? 0 : MIN(rm
->rm_col
[x
].rc_size
,
864 rm
->rm_col
[c
].rc_size
);
866 src
= rm
->rm_col
[c
].rc_abd
;
867 dst
= rm
->rm_col
[x
].rc_abd
;
869 if (c
== rm
->rm_firstdatacol
) {
870 abd_copy(dst
, src
, size
);
871 if (rm
->rm_col
[x
].rc_size
> size
)
872 abd_zero_off(dst
, size
,
873 rm
->rm_col
[x
].rc_size
- size
);
876 ASSERT3U(size
, <=, rm
->rm_col
[x
].rc_size
);
877 (void) abd_iterate_func2(dst
, src
, 0, 0, size
,
878 vdev_raidz_reconst_q_pre_func
, NULL
);
879 (void) abd_iterate_func(dst
,
880 size
, rm
->rm_col
[x
].rc_size
- size
,
881 vdev_raidz_reconst_q_pre_tail_func
, NULL
);
885 src
= rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
;
886 dst
= rm
->rm_col
[x
].rc_abd
;
887 exp
= 255 - (rm
->rm_cols
- 1 - x
);
888 rq
.q
= abd_to_buf(src
);
891 (void) abd_iterate_func(dst
, 0, rm
->rm_col
[x
].rc_size
,
892 vdev_raidz_reconst_q_post_func
, &rq
);
894 return (1 << VDEV_RAIDZ_Q
);
898 vdev_raidz_reconstruct_pq(raidz_map_t
*rm
, int *tgts
, int ntgts
)
900 uint8_t *p
, *q
, *pxy
, *qxy
, tmp
, a
, b
, aexp
, bexp
;
901 abd_t
*pdata
, *qdata
;
902 uint64_t xsize
, ysize
;
906 struct reconst_pq_struct rpq
;
910 ASSERT(x
>= rm
->rm_firstdatacol
);
911 ASSERT(y
< rm
->rm_cols
);
913 ASSERT(rm
->rm_col
[x
].rc_size
>= rm
->rm_col
[y
].rc_size
);
916 * Move the parity data aside -- we're going to compute parity as
917 * though columns x and y were full of zeros -- Pxy and Qxy. We want to
918 * reuse the parity generation mechanism without trashing the actual
919 * parity so we make those columns appear to be full of zeros by
920 * setting their lengths to zero.
922 pdata
= rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
;
923 qdata
= rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
;
924 xsize
= rm
->rm_col
[x
].rc_size
;
925 ysize
= rm
->rm_col
[y
].rc_size
;
927 rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
=
928 abd_alloc_linear(rm
->rm_col
[VDEV_RAIDZ_P
].rc_size
, B_TRUE
);
929 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
=
930 abd_alloc_linear(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_size
, B_TRUE
);
931 rm
->rm_col
[x
].rc_size
= 0;
932 rm
->rm_col
[y
].rc_size
= 0;
934 vdev_raidz_generate_parity_pq(rm
);
936 rm
->rm_col
[x
].rc_size
= xsize
;
937 rm
->rm_col
[y
].rc_size
= ysize
;
939 p
= abd_to_buf(pdata
);
940 q
= abd_to_buf(qdata
);
941 pxy
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
942 qxy
= abd_to_buf(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
943 xd
= rm
->rm_col
[x
].rc_abd
;
944 yd
= rm
->rm_col
[y
].rc_abd
;
948 * Pxy = P + D_x + D_y
949 * Qxy = Q + 2^(ndevs - 1 - x) * D_x + 2^(ndevs - 1 - y) * D_y
951 * We can then solve for D_x:
952 * D_x = A * (P + Pxy) + B * (Q + Qxy)
954 * A = 2^(x - y) * (2^(x - y) + 1)^-1
955 * B = 2^(ndevs - 1 - x) * (2^(x - y) + 1)^-1
957 * With D_x in hand, we can easily solve for D_y:
958 * D_y = P + Pxy + D_x
961 a
= vdev_raidz_pow2
[255 + x
- y
];
962 b
= vdev_raidz_pow2
[255 - (rm
->rm_cols
- 1 - x
)];
963 tmp
= 255 - vdev_raidz_log2
[a
^ 1];
965 aexp
= vdev_raidz_log2
[vdev_raidz_exp2(a
, tmp
)];
966 bexp
= vdev_raidz_log2
[vdev_raidz_exp2(b
, tmp
)];
968 ASSERT3U(xsize
, >=, ysize
);
976 (void) abd_iterate_func2(xd
, yd
, 0, 0, ysize
,
977 vdev_raidz_reconst_pq_func
, &rpq
);
978 (void) abd_iterate_func(xd
, ysize
, xsize
- ysize
,
979 vdev_raidz_reconst_pq_tail_func
, &rpq
);
981 abd_free(rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
);
982 abd_free(rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
);
985 * Restore the saved parity data.
987 rm
->rm_col
[VDEV_RAIDZ_P
].rc_abd
= pdata
;
988 rm
->rm_col
[VDEV_RAIDZ_Q
].rc_abd
= qdata
;
990 return ((1 << VDEV_RAIDZ_P
) | (1 << VDEV_RAIDZ_Q
));
995 * In the general case of reconstruction, we must solve the system of linear
996 * equations defined by the coeffecients used to generate parity as well as
997 * the contents of the data and parity disks. This can be expressed with
998 * vectors for the original data (D) and the actual data (d) and parity (p)
999 * and a matrix composed of the identity matrix (I) and a dispersal matrix (V):
1003 * | V | | D_0 | | p_m-1 |
1004 * | | x | : | = | d_0 |
1005 * | I | | D_n-1 | | : |
1006 * | | ~~ ~~ | d_n-1 |
1009 * I is simply a square identity matrix of size n, and V is a vandermonde
1010 * matrix defined by the coeffecients we chose for the various parity columns
1011 * (1, 2, 4). Note that these values were chosen both for simplicity, speedy
1012 * computation as well as linear separability.
1015 * | 1 .. 1 1 1 | | p_0 |
1016 * | 2^n-1 .. 4 2 1 | __ __ | : |
1017 * | 4^n-1 .. 16 4 1 | | D_0 | | p_m-1 |
1018 * | 1 .. 0 0 0 | | D_1 | | d_0 |
1019 * | 0 .. 0 0 0 | x | D_2 | = | d_1 |
1020 * | : : : : | | : | | d_2 |
1021 * | 0 .. 1 0 0 | | D_n-1 | | : |
1022 * | 0 .. 0 1 0 | ~~ ~~ | : |
1023 * | 0 .. 0 0 1 | | d_n-1 |
1026 * Note that I, V, d, and p are known. To compute D, we must invert the
1027 * matrix and use the known data and parity values to reconstruct the unknown
1028 * data values. We begin by removing the rows in V|I and d|p that correspond
1029 * to failed or missing columns; we then make V|I square (n x n) and d|p
1030 * sized n by removing rows corresponding to unused parity from the bottom up
1031 * to generate (V|I)' and (d|p)'. We can then generate the inverse of (V|I)'
1032 * using Gauss-Jordan elimination. In the example below we use m=3 parity
1033 * columns, n=8 data columns, with errors in d_1, d_2, and p_1:
1035 * | 1 1 1 1 1 1 1 1 |
1036 * | 128 64 32 16 8 4 2 1 | <-----+-+-- missing disks
1037 * | 19 205 116 29 64 16 4 1 | / /
1038 * | 1 0 0 0 0 0 0 0 | / /
1039 * | 0 1 0 0 0 0 0 0 | <--' /
1040 * (V|I) = | 0 0 1 0 0 0 0 0 | <---'
1041 * | 0 0 0 1 0 0 0 0 |
1042 * | 0 0 0 0 1 0 0 0 |
1043 * | 0 0 0 0 0 1 0 0 |
1044 * | 0 0 0 0 0 0 1 0 |
1045 * | 0 0 0 0 0 0 0 1 |
1048 * | 1 1 1 1 1 1 1 1 |
1049 * | 128 64 32 16 8 4 2 1 |
1050 * | 19 205 116 29 64 16 4 1 |
1051 * | 1 0 0 0 0 0 0 0 |
1052 * | 0 1 0 0 0 0 0 0 |
1053 * (V|I)' = | 0 0 1 0 0 0 0 0 |
1054 * | 0 0 0 1 0 0 0 0 |
1055 * | 0 0 0 0 1 0 0 0 |
1056 * | 0 0 0 0 0 1 0 0 |
1057 * | 0 0 0 0 0 0 1 0 |
1058 * | 0 0 0 0 0 0 0 1 |
1061 * Here we employ Gauss-Jordan elimination to find the inverse of (V|I)'. We
1062 * have carefully chosen the seed values 1, 2, and 4 to ensure that this
1063 * matrix is not singular.
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 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1068 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1069 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1070 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1071 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1072 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1075 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1076 * | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 |
1077 * | 19 205 116 29 64 16 4 1 0 1 0 0 0 0 0 0 |
1078 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1079 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1080 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1081 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1082 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1085 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1086 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1087 * | 0 205 116 0 0 0 0 0 0 1 19 29 64 16 4 1 |
1088 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1089 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1090 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1091 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1092 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1095 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1096 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1097 * | 0 0 185 0 0 0 0 0 205 1 222 208 141 221 201 204 |
1098 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1099 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1100 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1101 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1102 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1105 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1106 * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 |
1107 * | 0 0 1 0 0 0 0 0 166 100 4 40 158 168 216 209 |
1108 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1109 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1110 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1111 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1112 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1115 * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 |
1116 * | 0 1 0 0 0 0 0 0 167 100 5 41 159 169 217 208 |
1117 * | 0 0 1 0 0 0 0 0 166 100 4 40 158 168 216 209 |
1118 * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 |
1119 * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 |
1120 * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 |
1121 * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 |
1122 * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 |
1125 * | 0 0 1 0 0 0 0 0 |
1126 * | 167 100 5 41 159 169 217 208 |
1127 * | 166 100 4 40 158 168 216 209 |
1128 * (V|I)'^-1 = | 0 0 0 1 0 0 0 0 |
1129 * | 0 0 0 0 1 0 0 0 |
1130 * | 0 0 0 0 0 1 0 0 |
1131 * | 0 0 0 0 0 0 1 0 |
1132 * | 0 0 0 0 0 0 0 1 |
1135 * We can then simply compute D = (V|I)'^-1 x (d|p)' to discover the values
1136 * of the missing data.
1138 * As is apparent from the example above, the only non-trivial rows in the
1139 * inverse matrix correspond to the data disks that we're trying to
1140 * reconstruct. Indeed, those are the only rows we need as the others would
1141 * only be useful for reconstructing data known or assumed to be valid. For
1142 * that reason, we only build the coefficients in the rows that correspond to
1148 vdev_raidz_matrix_init(raidz_map_t
*rm
, int n
, int nmap
, int *map
,
1154 ASSERT(n
== rm
->rm_cols
- rm
->rm_firstdatacol
);
1157 * Fill in the missing rows of interest.
1159 for (i
= 0; i
< nmap
; i
++) {
1160 ASSERT3S(0, <=, map
[i
]);
1161 ASSERT3S(map
[i
], <=, 2);
1168 for (j
= 0; j
< n
; j
++) {
1172 rows
[i
][j
] = vdev_raidz_pow2
[pow
];
1178 vdev_raidz_matrix_invert(raidz_map_t
*rm
, int n
, int nmissing
, int *missing
,
1179 uint8_t **rows
, uint8_t **invrows
, const uint8_t *used
)
1185 * Assert that the first nmissing entries from the array of used
1186 * columns correspond to parity columns and that subsequent entries
1187 * correspond to data columns.
1189 for (i
= 0; i
< nmissing
; i
++) {
1190 ASSERT3S(used
[i
], <, rm
->rm_firstdatacol
);
1192 for (; i
< n
; i
++) {
1193 ASSERT3S(used
[i
], >=, rm
->rm_firstdatacol
);
1197 * First initialize the storage where we'll compute the inverse rows.
1199 for (i
= 0; i
< nmissing
; i
++) {
1200 for (j
= 0; j
< n
; j
++) {
1201 invrows
[i
][j
] = (i
== j
) ? 1 : 0;
1206 * Subtract all trivial rows from the rows of consequence.
1208 for (i
= 0; i
< nmissing
; i
++) {
1209 for (j
= nmissing
; j
< n
; j
++) {
1210 ASSERT3U(used
[j
], >=, rm
->rm_firstdatacol
);
1211 jj
= used
[j
] - rm
->rm_firstdatacol
;
1213 invrows
[i
][j
] = rows
[i
][jj
];
1219 * For each of the rows of interest, we must normalize it and subtract
1220 * a multiple of it from the other rows.
1222 for (i
= 0; i
< nmissing
; i
++) {
1223 for (j
= 0; j
< missing
[i
]; j
++) {
1224 ASSERT0(rows
[i
][j
]);
1226 ASSERT3U(rows
[i
][missing
[i
]], !=, 0);
1229 * Compute the inverse of the first element and multiply each
1230 * element in the row by that value.
1232 log
= 255 - vdev_raidz_log2
[rows
[i
][missing
[i
]]];
1234 for (j
= 0; j
< n
; j
++) {
1235 rows
[i
][j
] = vdev_raidz_exp2(rows
[i
][j
], log
);
1236 invrows
[i
][j
] = vdev_raidz_exp2(invrows
[i
][j
], log
);
1239 for (ii
= 0; ii
< nmissing
; ii
++) {
1243 ASSERT3U(rows
[ii
][missing
[i
]], !=, 0);
1245 log
= vdev_raidz_log2
[rows
[ii
][missing
[i
]]];
1247 for (j
= 0; j
< n
; j
++) {
1249 vdev_raidz_exp2(rows
[i
][j
], log
);
1251 vdev_raidz_exp2(invrows
[i
][j
], log
);
1257 * Verify that the data that is left in the rows are properly part of
1258 * an identity matrix.
1260 for (i
= 0; i
< nmissing
; i
++) {
1261 for (j
= 0; j
< n
; j
++) {
1262 if (j
== missing
[i
]) {
1263 ASSERT3U(rows
[i
][j
], ==, 1);
1265 ASSERT0(rows
[i
][j
]);
1272 vdev_raidz_matrix_reconstruct(raidz_map_t
*rm
, int n
, int nmissing
,
1273 int *missing
, uint8_t **invrows
, const uint8_t *used
)
1278 uint8_t *dst
[VDEV_RAIDZ_MAXPARITY
] = { NULL
};
1279 uint64_t dcount
[VDEV_RAIDZ_MAXPARITY
] = { 0 };
1283 uint8_t *invlog
[VDEV_RAIDZ_MAXPARITY
];
1287 psize
= sizeof (invlog
[0][0]) * n
* nmissing
;
1288 p
= kmem_alloc(psize
, KM_SLEEP
);
1290 for (pp
= p
, i
= 0; i
< nmissing
; i
++) {
1295 for (i
= 0; i
< nmissing
; i
++) {
1296 for (j
= 0; j
< n
; j
++) {
1297 ASSERT3U(invrows
[i
][j
], !=, 0);
1298 invlog
[i
][j
] = vdev_raidz_log2
[invrows
[i
][j
]];
1302 for (i
= 0; i
< n
; i
++) {
1304 ASSERT3U(c
, <, rm
->rm_cols
);
1306 src
= abd_to_buf(rm
->rm_col
[c
].rc_abd
);
1307 ccount
= rm
->rm_col
[c
].rc_size
;
1308 for (j
= 0; j
< nmissing
; j
++) {
1309 cc
= missing
[j
] + rm
->rm_firstdatacol
;
1310 ASSERT3U(cc
, >=, rm
->rm_firstdatacol
);
1311 ASSERT3U(cc
, <, rm
->rm_cols
);
1312 ASSERT3U(cc
, !=, c
);
1314 dst
[j
] = abd_to_buf(rm
->rm_col
[cc
].rc_abd
);
1315 dcount
[j
] = rm
->rm_col
[cc
].rc_size
;
1318 ASSERT(ccount
>= rm
->rm_col
[missing
[0]].rc_size
|| i
> 0);
1320 for (x
= 0; x
< ccount
; x
++, src
++) {
1322 log
= vdev_raidz_log2
[*src
];
1324 for (cc
= 0; cc
< nmissing
; cc
++) {
1325 if (x
>= dcount
[cc
])
1331 if ((ll
= log
+ invlog
[cc
][i
]) >= 255)
1333 val
= vdev_raidz_pow2
[ll
];
1344 kmem_free(p
, psize
);
1348 vdev_raidz_reconstruct_general(raidz_map_t
*rm
, int *tgts
, int ntgts
)
1352 int missing_rows
[VDEV_RAIDZ_MAXPARITY
];
1353 int parity_map
[VDEV_RAIDZ_MAXPARITY
];
1358 uint8_t *rows
[VDEV_RAIDZ_MAXPARITY
];
1359 uint8_t *invrows
[VDEV_RAIDZ_MAXPARITY
];
1362 abd_t
**bufs
= NULL
;
1367 * Matrix reconstruction can't use scatter ABDs yet, so we allocate
1368 * temporary linear ABDs.
1370 if (!abd_is_linear(rm
->rm_col
[rm
->rm_firstdatacol
].rc_abd
)) {
1371 bufs
= kmem_alloc(rm
->rm_cols
* sizeof (abd_t
*), KM_PUSHPAGE
);
1373 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
1374 raidz_col_t
*col
= &rm
->rm_col
[c
];
1376 bufs
[c
] = col
->rc_abd
;
1377 col
->rc_abd
= abd_alloc_linear(col
->rc_size
, B_TRUE
);
1378 abd_copy(col
->rc_abd
, bufs
[c
], col
->rc_size
);
1382 n
= rm
->rm_cols
- rm
->rm_firstdatacol
;
1385 * Figure out which data columns are missing.
1388 for (t
= 0; t
< ntgts
; t
++) {
1389 if (tgts
[t
] >= rm
->rm_firstdatacol
) {
1390 missing_rows
[nmissing_rows
++] =
1391 tgts
[t
] - rm
->rm_firstdatacol
;
1396 * Figure out which parity columns to use to help generate the missing
1399 for (tt
= 0, c
= 0, i
= 0; i
< nmissing_rows
; c
++) {
1401 ASSERT(c
< rm
->rm_firstdatacol
);
1404 * Skip any targeted parity columns.
1406 if (c
== tgts
[tt
]) {
1418 ASSERT3U(code
, <, 1 << VDEV_RAIDZ_MAXPARITY
);
1420 psize
= (sizeof (rows
[0][0]) + sizeof (invrows
[0][0])) *
1421 nmissing_rows
* n
+ sizeof (used
[0]) * n
;
1422 p
= kmem_alloc(psize
, KM_SLEEP
);
1424 for (pp
= p
, i
= 0; i
< nmissing_rows
; i
++) {
1432 for (i
= 0; i
< nmissing_rows
; i
++) {
1433 used
[i
] = parity_map
[i
];
1436 for (tt
= 0, c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
1437 if (tt
< nmissing_rows
&&
1438 c
== missing_rows
[tt
] + rm
->rm_firstdatacol
) {
1449 * Initialize the interesting rows of the matrix.
1451 vdev_raidz_matrix_init(rm
, n
, nmissing_rows
, parity_map
, rows
);
1454 * Invert the matrix.
1456 vdev_raidz_matrix_invert(rm
, n
, nmissing_rows
, missing_rows
, rows
,
1460 * Reconstruct the missing data using the generated matrix.
1462 vdev_raidz_matrix_reconstruct(rm
, n
, nmissing_rows
, missing_rows
,
1465 kmem_free(p
, psize
);
1468 * copy back from temporary linear abds and free them
1471 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
1472 raidz_col_t
*col
= &rm
->rm_col
[c
];
1474 abd_copy(bufs
[c
], col
->rc_abd
, col
->rc_size
);
1475 abd_free(col
->rc_abd
);
1476 col
->rc_abd
= bufs
[c
];
1478 kmem_free(bufs
, rm
->rm_cols
* sizeof (abd_t
*));
1485 vdev_raidz_reconstruct(raidz_map_t
*rm
, const int *t
, int nt
)
1487 int tgts
[VDEV_RAIDZ_MAXPARITY
], *dt
;
1491 int nbadparity
, nbaddata
;
1492 int parity_valid
[VDEV_RAIDZ_MAXPARITY
];
1495 * The tgts list must already be sorted.
1497 for (i
= 1; i
< nt
; i
++) {
1498 ASSERT(t
[i
] > t
[i
- 1]);
1501 nbadparity
= rm
->rm_firstdatacol
;
1502 nbaddata
= rm
->rm_cols
- nbadparity
;
1504 for (i
= 0, c
= 0; c
< rm
->rm_cols
; c
++) {
1505 if (c
< rm
->rm_firstdatacol
)
1506 parity_valid
[c
] = B_FALSE
;
1508 if (i
< nt
&& c
== t
[i
]) {
1511 } else if (rm
->rm_col
[c
].rc_error
!= 0) {
1513 } else if (c
>= rm
->rm_firstdatacol
) {
1516 parity_valid
[c
] = B_TRUE
;
1521 ASSERT(ntgts
>= nt
);
1522 ASSERT(nbaddata
>= 0);
1523 ASSERT(nbaddata
+ nbadparity
== ntgts
);
1525 dt
= &tgts
[nbadparity
];
1527 /* Reconstruct using the new math implementation */
1528 ret
= vdev_raidz_math_reconstruct(rm
, parity_valid
, dt
, nbaddata
);
1529 if (ret
!= RAIDZ_ORIGINAL_IMPL
)
1533 * See if we can use any of our optimized reconstruction routines.
1537 if (parity_valid
[VDEV_RAIDZ_P
])
1538 return (vdev_raidz_reconstruct_p(rm
, dt
, 1));
1540 ASSERT(rm
->rm_firstdatacol
> 1);
1542 if (parity_valid
[VDEV_RAIDZ_Q
])
1543 return (vdev_raidz_reconstruct_q(rm
, dt
, 1));
1545 ASSERT(rm
->rm_firstdatacol
> 2);
1549 ASSERT(rm
->rm_firstdatacol
> 1);
1551 if (parity_valid
[VDEV_RAIDZ_P
] &&
1552 parity_valid
[VDEV_RAIDZ_Q
])
1553 return (vdev_raidz_reconstruct_pq(rm
, dt
, 2));
1555 ASSERT(rm
->rm_firstdatacol
> 2);
1560 code
= vdev_raidz_reconstruct_general(rm
, tgts
, ntgts
);
1561 ASSERT(code
< (1 << VDEV_RAIDZ_MAXPARITY
));
1567 vdev_raidz_open(vdev_t
*vd
, uint64_t *asize
, uint64_t *max_asize
,
1571 uint64_t nparity
= vd
->vdev_nparity
;
1576 ASSERT(nparity
> 0);
1578 if (nparity
> VDEV_RAIDZ_MAXPARITY
||
1579 vd
->vdev_children
< nparity
+ 1) {
1580 vd
->vdev_stat
.vs_aux
= VDEV_AUX_BAD_LABEL
;
1581 return (SET_ERROR(EINVAL
));
1584 vdev_open_children(vd
);
1586 for (c
= 0; c
< vd
->vdev_children
; c
++) {
1587 cvd
= vd
->vdev_child
[c
];
1589 if (cvd
->vdev_open_error
!= 0) {
1590 lasterror
= cvd
->vdev_open_error
;
1595 *asize
= MIN(*asize
- 1, cvd
->vdev_asize
- 1) + 1;
1596 *max_asize
= MIN(*max_asize
- 1, cvd
->vdev_max_asize
- 1) + 1;
1597 *ashift
= MAX(*ashift
, cvd
->vdev_ashift
);
1600 *asize
*= vd
->vdev_children
;
1601 *max_asize
*= vd
->vdev_children
;
1603 if (numerrors
> nparity
) {
1604 vd
->vdev_stat
.vs_aux
= VDEV_AUX_NO_REPLICAS
;
1612 vdev_raidz_close(vdev_t
*vd
)
1616 for (c
= 0; c
< vd
->vdev_children
; c
++)
1617 vdev_close(vd
->vdev_child
[c
]);
1621 vdev_raidz_asize(vdev_t
*vd
, uint64_t psize
)
1624 uint64_t ashift
= vd
->vdev_top
->vdev_ashift
;
1625 uint64_t cols
= vd
->vdev_children
;
1626 uint64_t nparity
= vd
->vdev_nparity
;
1628 asize
= ((psize
- 1) >> ashift
) + 1;
1629 asize
+= nparity
* ((asize
+ cols
- nparity
- 1) / (cols
- nparity
));
1630 asize
= roundup(asize
, nparity
+ 1) << ashift
;
1636 vdev_raidz_child_done(zio_t
*zio
)
1638 raidz_col_t
*rc
= zio
->io_private
;
1640 rc
->rc_error
= zio
->io_error
;
1646 * Start an IO operation on a RAIDZ VDev
1649 * - For write operations:
1650 * 1. Generate the parity data
1651 * 2. Create child zio write operations to each column's vdev, for both
1653 * 3. If the column skips any sectors for padding, create optional dummy
1654 * write zio children for those areas to improve aggregation continuity.
1655 * - For read operations:
1656 * 1. Create child zio read operations to each data column's vdev to read
1657 * the range of data required for zio.
1658 * 2. If this is a scrub or resilver operation, or if any of the data
1659 * vdevs have had errors, then create zio read operations to the parity
1660 * columns' VDevs as well.
1663 vdev_raidz_io_start(zio_t
*zio
)
1665 vdev_t
*vd
= zio
->io_vd
;
1666 vdev_t
*tvd
= vd
->vdev_top
;
1672 rm
= vdev_raidz_map_alloc(zio
, tvd
->vdev_ashift
, vd
->vdev_children
,
1675 ASSERT3U(rm
->rm_asize
, ==, vdev_psize_to_asize(vd
, zio
->io_size
));
1677 if (zio
->io_type
== ZIO_TYPE_WRITE
) {
1678 vdev_raidz_generate_parity(rm
);
1680 for (c
= 0; c
< rm
->rm_cols
; c
++) {
1681 rc
= &rm
->rm_col
[c
];
1682 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1683 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
1684 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
1685 zio
->io_type
, zio
->io_priority
, 0,
1686 vdev_raidz_child_done
, rc
));
1690 * Generate optional I/Os for any skipped sectors to improve
1691 * aggregation contiguity.
1693 for (c
= rm
->rm_skipstart
, i
= 0; i
< rm
->rm_nskip
; c
++, i
++) {
1694 ASSERT(c
<= rm
->rm_scols
);
1695 if (c
== rm
->rm_scols
)
1697 rc
= &rm
->rm_col
[c
];
1698 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1699 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
1700 rc
->rc_offset
+ rc
->rc_size
, NULL
,
1701 1 << tvd
->vdev_ashift
,
1702 zio
->io_type
, zio
->io_priority
,
1703 ZIO_FLAG_NODATA
| ZIO_FLAG_OPTIONAL
, NULL
, NULL
));
1710 ASSERT(zio
->io_type
== ZIO_TYPE_READ
);
1713 * Iterate over the columns in reverse order so that we hit the parity
1714 * last -- any errors along the way will force us to read the parity.
1716 for (c
= rm
->rm_cols
- 1; c
>= 0; c
--) {
1717 rc
= &rm
->rm_col
[c
];
1718 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
1719 if (!vdev_readable(cvd
)) {
1720 if (c
>= rm
->rm_firstdatacol
)
1721 rm
->rm_missingdata
++;
1723 rm
->rm_missingparity
++;
1724 rc
->rc_error
= SET_ERROR(ENXIO
);
1725 rc
->rc_tried
= 1; /* don't even try */
1729 if (vdev_dtl_contains(cvd
, DTL_MISSING
, zio
->io_txg
, 1)) {
1730 if (c
>= rm
->rm_firstdatacol
)
1731 rm
->rm_missingdata
++;
1733 rm
->rm_missingparity
++;
1734 rc
->rc_error
= SET_ERROR(ESTALE
);
1738 if (c
>= rm
->rm_firstdatacol
|| rm
->rm_missingdata
> 0 ||
1739 (zio
->io_flags
& (ZIO_FLAG_SCRUB
| ZIO_FLAG_RESILVER
))) {
1740 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
1741 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
1742 zio
->io_type
, zio
->io_priority
, 0,
1743 vdev_raidz_child_done
, rc
));
1752 * Report a checksum error for a child of a RAID-Z device.
1755 raidz_checksum_error(zio_t
*zio
, raidz_col_t
*rc
, void *bad_data
)
1758 vdev_t
*vd
= zio
->io_vd
->vdev_child
[rc
->rc_devidx
];
1760 if (!(zio
->io_flags
& ZIO_FLAG_SPECULATIVE
)) {
1761 zio_bad_cksum_t zbc
;
1762 raidz_map_t
*rm
= zio
->io_vsd
;
1764 mutex_enter(&vd
->vdev_stat_lock
);
1765 vd
->vdev_stat
.vs_checksum_errors
++;
1766 mutex_exit(&vd
->vdev_stat_lock
);
1768 zbc
.zbc_has_cksum
= 0;
1769 zbc
.zbc_injected
= rm
->rm_ecksuminjected
;
1771 buf
= abd_borrow_buf_copy(rc
->rc_abd
, rc
->rc_size
);
1772 zfs_ereport_post_checksum(zio
->io_spa
, vd
, zio
,
1773 rc
->rc_offset
, rc
->rc_size
, buf
, bad_data
,
1775 abd_return_buf(rc
->rc_abd
, buf
, rc
->rc_size
);
1780 * We keep track of whether or not there were any injected errors, so that
1781 * any ereports we generate can note it.
1784 raidz_checksum_verify(zio_t
*zio
)
1786 zio_bad_cksum_t zbc
;
1787 raidz_map_t
*rm
= zio
->io_vsd
;
1790 bzero(&zbc
, sizeof (zio_bad_cksum_t
));
1792 ret
= zio_checksum_error(zio
, &zbc
);
1793 if (ret
!= 0 && zbc
.zbc_injected
!= 0)
1794 rm
->rm_ecksuminjected
= 1;
1800 * Generate the parity from the data columns. If we tried and were able to
1801 * read the parity without error, verify that the generated parity matches the
1802 * data we read. If it doesn't, we fire off a checksum error. Return the
1803 * number such failures.
1806 raidz_parity_verify(zio_t
*zio
, raidz_map_t
*rm
)
1808 void *orig
[VDEV_RAIDZ_MAXPARITY
];
1812 blkptr_t
*bp
= zio
->io_bp
;
1813 enum zio_checksum checksum
= (bp
== NULL
? zio
->io_prop
.zp_checksum
:
1814 (BP_IS_GANG(bp
) ? ZIO_CHECKSUM_GANG_HEADER
: BP_GET_CHECKSUM(bp
)));
1816 if (checksum
== ZIO_CHECKSUM_NOPARITY
)
1819 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++) {
1820 rc
= &rm
->rm_col
[c
];
1821 if (!rc
->rc_tried
|| rc
->rc_error
!= 0)
1823 orig
[c
] = zio_buf_alloc(rc
->rc_size
);
1824 abd_copy_to_buf(orig
[c
], rc
->rc_abd
, rc
->rc_size
);
1827 vdev_raidz_generate_parity(rm
);
1829 for (c
= 0; c
< rm
->rm_firstdatacol
; c
++) {
1830 rc
= &rm
->rm_col
[c
];
1831 if (!rc
->rc_tried
|| rc
->rc_error
!= 0)
1833 if (bcmp(orig
[c
], abd_to_buf(rc
->rc_abd
), rc
->rc_size
) != 0) {
1834 raidz_checksum_error(zio
, rc
, orig
[c
]);
1835 rc
->rc_error
= SET_ERROR(ECKSUM
);
1838 zio_buf_free(orig
[c
], rc
->rc_size
);
1845 vdev_raidz_worst_error(raidz_map_t
*rm
)
1849 for (c
= 0; c
< rm
->rm_cols
; c
++)
1850 error
= zio_worst_error(error
, rm
->rm_col
[c
].rc_error
);
1856 * Iterate over all combinations of bad data and attempt a reconstruction.
1857 * Note that the algorithm below is non-optimal because it doesn't take into
1858 * account how reconstruction is actually performed. For example, with
1859 * triple-parity RAID-Z the reconstruction procedure is the same if column 4
1860 * is targeted as invalid as if columns 1 and 4 are targeted since in both
1861 * cases we'd only use parity information in column 0.
1864 vdev_raidz_combrec(zio_t
*zio
, int total_errors
, int data_errors
)
1866 raidz_map_t
*rm
= zio
->io_vsd
;
1868 void *orig
[VDEV_RAIDZ_MAXPARITY
];
1869 int tstore
[VDEV_RAIDZ_MAXPARITY
+ 2];
1870 int *tgts
= &tstore
[1];
1871 int curr
, next
, i
, c
, n
;
1874 ASSERT(total_errors
< rm
->rm_firstdatacol
);
1877 * This simplifies one edge condition.
1881 for (n
= 1; n
<= rm
->rm_firstdatacol
- total_errors
; n
++) {
1883 * Initialize the targets array by finding the first n columns
1884 * that contain no error.
1886 * If there were no data errors, we need to ensure that we're
1887 * always explicitly attempting to reconstruct at least one
1888 * data column. To do this, we simply push the highest target
1889 * up into the data columns.
1891 for (c
= 0, i
= 0; i
< n
; i
++) {
1892 if (i
== n
- 1 && data_errors
== 0 &&
1893 c
< rm
->rm_firstdatacol
) {
1894 c
= rm
->rm_firstdatacol
;
1897 while (rm
->rm_col
[c
].rc_error
!= 0) {
1899 ASSERT3S(c
, <, rm
->rm_cols
);
1906 * Setting tgts[n] simplifies the other edge condition.
1908 tgts
[n
] = rm
->rm_cols
;
1911 * These buffers were allocated in previous iterations.
1913 for (i
= 0; i
< n
- 1; i
++) {
1914 ASSERT(orig
[i
] != NULL
);
1917 orig
[n
- 1] = zio_buf_alloc(rm
->rm_col
[0].rc_size
);
1927 * Save off the original data that we're going to
1928 * attempt to reconstruct.
1930 for (i
= 0; i
< n
; i
++) {
1931 ASSERT(orig
[i
] != NULL
);
1934 ASSERT3S(c
, <, rm
->rm_cols
);
1935 rc
= &rm
->rm_col
[c
];
1936 abd_copy_to_buf(orig
[i
], rc
->rc_abd
,
1941 * Attempt a reconstruction and exit the outer loop on
1944 code
= vdev_raidz_reconstruct(rm
, tgts
, n
);
1945 if (raidz_checksum_verify(zio
) == 0) {
1947 for (i
= 0; i
< n
; i
++) {
1949 rc
= &rm
->rm_col
[c
];
1950 ASSERT(rc
->rc_error
== 0);
1952 raidz_checksum_error(zio
, rc
,
1954 rc
->rc_error
= SET_ERROR(ECKSUM
);
1962 * Restore the original data.
1964 for (i
= 0; i
< n
; i
++) {
1966 rc
= &rm
->rm_col
[c
];
1967 abd_copy_from_buf(rc
->rc_abd
, orig
[i
],
1973 * Find the next valid column after the curr
1976 for (next
= tgts
[curr
] + 1;
1977 next
< rm
->rm_cols
&&
1978 rm
->rm_col
[next
].rc_error
!= 0; next
++)
1981 ASSERT(next
<= tgts
[curr
+ 1]);
1984 * If that spot is available, we're done here.
1986 if (next
!= tgts
[curr
+ 1])
1990 * Otherwise, find the next valid column after
1991 * the previous position.
1993 for (c
= tgts
[curr
- 1] + 1;
1994 rm
->rm_col
[c
].rc_error
!= 0; c
++)
2000 } while (curr
!= n
);
2005 for (i
= 0; i
< n
; i
++) {
2006 zio_buf_free(orig
[i
], rm
->rm_col
[0].rc_size
);
2013 * Complete an IO operation on a RAIDZ VDev
2016 * - For write operations:
2017 * 1. Check for errors on the child IOs.
2018 * 2. Return, setting an error code if too few child VDevs were written
2019 * to reconstruct the data later. Note that partial writes are
2020 * considered successful if they can be reconstructed at all.
2021 * - For read operations:
2022 * 1. Check for errors on the child IOs.
2023 * 2. If data errors occurred:
2024 * a. Try to reassemble the data from the parity available.
2025 * b. If we haven't yet read the parity drives, read them now.
2026 * c. If all parity drives have been read but the data still doesn't
2027 * reassemble with a correct checksum, then try combinatorial
2029 * d. If that doesn't work, return an error.
2030 * 3. If there were unexpected errors or this is a resilver operation,
2031 * rewrite the vdevs that had errors.
2034 vdev_raidz_io_done(zio_t
*zio
)
2036 vdev_t
*vd
= zio
->io_vd
;
2038 raidz_map_t
*rm
= zio
->io_vsd
;
2039 raidz_col_t
*rc
= NULL
;
2040 int unexpected_errors
= 0;
2041 int parity_errors
= 0;
2042 int parity_untried
= 0;
2043 int data_errors
= 0;
2044 int total_errors
= 0;
2046 int tgts
[VDEV_RAIDZ_MAXPARITY
];
2049 ASSERT(zio
->io_bp
!= NULL
); /* XXX need to add code to enforce this */
2051 ASSERT(rm
->rm_missingparity
<= rm
->rm_firstdatacol
);
2052 ASSERT(rm
->rm_missingdata
<= rm
->rm_cols
- rm
->rm_firstdatacol
);
2054 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2055 rc
= &rm
->rm_col
[c
];
2058 ASSERT(rc
->rc_error
!= ECKSUM
); /* child has no bp */
2060 if (c
< rm
->rm_firstdatacol
)
2065 if (!rc
->rc_skipped
)
2066 unexpected_errors
++;
2069 } else if (c
< rm
->rm_firstdatacol
&& !rc
->rc_tried
) {
2074 if (zio
->io_type
== ZIO_TYPE_WRITE
) {
2076 * XXX -- for now, treat partial writes as a success.
2077 * (If we couldn't write enough columns to reconstruct
2078 * the data, the I/O failed. Otherwise, good enough.)
2080 * Now that we support write reallocation, it would be better
2081 * to treat partial failure as real failure unless there are
2082 * no non-degraded top-level vdevs left, and not update DTLs
2083 * if we intend to reallocate.
2086 if (total_errors
> rm
->rm_firstdatacol
)
2087 zio
->io_error
= vdev_raidz_worst_error(rm
);
2092 ASSERT(zio
->io_type
== ZIO_TYPE_READ
);
2094 * There are three potential phases for a read:
2095 * 1. produce valid data from the columns read
2096 * 2. read all disks and try again
2097 * 3. perform combinatorial reconstruction
2099 * Each phase is progressively both more expensive and less likely to
2100 * occur. If we encounter more errors than we can repair or all phases
2101 * fail, we have no choice but to return an error.
2105 * If the number of errors we saw was correctable -- less than or equal
2106 * to the number of parity disks read -- attempt to produce data that
2107 * has a valid checksum. Naturally, this case applies in the absence of
2110 if (total_errors
<= rm
->rm_firstdatacol
- parity_untried
) {
2111 if (data_errors
== 0) {
2112 if (raidz_checksum_verify(zio
) == 0) {
2114 * If we read parity information (unnecessarily
2115 * as it happens since no reconstruction was
2116 * needed) regenerate and verify the parity.
2117 * We also regenerate parity when resilvering
2118 * so we can write it out to the failed device
2121 if (parity_errors
+ parity_untried
<
2122 rm
->rm_firstdatacol
||
2123 (zio
->io_flags
& ZIO_FLAG_RESILVER
)) {
2124 n
= raidz_parity_verify(zio
, rm
);
2125 unexpected_errors
+= n
;
2126 ASSERT(parity_errors
+ n
<=
2127 rm
->rm_firstdatacol
);
2133 * We either attempt to read all the parity columns or
2134 * none of them. If we didn't try to read parity, we
2135 * wouldn't be here in the correctable case. There must
2136 * also have been fewer parity errors than parity
2137 * columns or, again, we wouldn't be in this code path.
2139 ASSERT(parity_untried
== 0);
2140 ASSERT(parity_errors
< rm
->rm_firstdatacol
);
2143 * Identify the data columns that reported an error.
2146 for (c
= rm
->rm_firstdatacol
; c
< rm
->rm_cols
; c
++) {
2147 rc
= &rm
->rm_col
[c
];
2148 if (rc
->rc_error
!= 0) {
2149 ASSERT(n
< VDEV_RAIDZ_MAXPARITY
);
2154 ASSERT(rm
->rm_firstdatacol
>= n
);
2156 code
= vdev_raidz_reconstruct(rm
, tgts
, n
);
2158 if (raidz_checksum_verify(zio
) == 0) {
2160 * If we read more parity disks than were used
2161 * for reconstruction, confirm that the other
2162 * parity disks produced correct data. This
2163 * routine is suboptimal in that it regenerates
2164 * the parity that we already used in addition
2165 * to the parity that we're attempting to
2166 * verify, but this should be a relatively
2167 * uncommon case, and can be optimized if it
2168 * becomes a problem. Note that we regenerate
2169 * parity when resilvering so we can write it
2170 * out to failed devices later.
2172 if (parity_errors
< rm
->rm_firstdatacol
- n
||
2173 (zio
->io_flags
& ZIO_FLAG_RESILVER
)) {
2174 n
= raidz_parity_verify(zio
, rm
);
2175 unexpected_errors
+= n
;
2176 ASSERT(parity_errors
+ n
<=
2177 rm
->rm_firstdatacol
);
2186 * This isn't a typical situation -- either we got a read error or
2187 * a child silently returned bad data. Read every block so we can
2188 * try again with as much data and parity as we can track down. If
2189 * we've already been through once before, all children will be marked
2190 * as tried so we'll proceed to combinatorial reconstruction.
2192 unexpected_errors
= 1;
2193 rm
->rm_missingdata
= 0;
2194 rm
->rm_missingparity
= 0;
2196 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2197 if (rm
->rm_col
[c
].rc_tried
)
2200 zio_vdev_io_redone(zio
);
2202 rc
= &rm
->rm_col
[c
];
2205 zio_nowait(zio_vdev_child_io(zio
, NULL
,
2206 vd
->vdev_child
[rc
->rc_devidx
],
2207 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
2208 zio
->io_type
, zio
->io_priority
, 0,
2209 vdev_raidz_child_done
, rc
));
2210 } while (++c
< rm
->rm_cols
);
2216 * At this point we've attempted to reconstruct the data given the
2217 * errors we detected, and we've attempted to read all columns. There
2218 * must, therefore, be one or more additional problems -- silent errors
2219 * resulting in invalid data rather than explicit I/O errors resulting
2220 * in absent data. We check if there is enough additional data to
2221 * possibly reconstruct the data and then perform combinatorial
2222 * reconstruction over all possible combinations. If that fails,
2225 if (total_errors
> rm
->rm_firstdatacol
) {
2226 zio
->io_error
= vdev_raidz_worst_error(rm
);
2228 } else if (total_errors
< rm
->rm_firstdatacol
&&
2229 (code
= vdev_raidz_combrec(zio
, total_errors
, data_errors
)) != 0) {
2231 * If we didn't use all the available parity for the
2232 * combinatorial reconstruction, verify that the remaining
2233 * parity is correct.
2235 if (code
!= (1 << rm
->rm_firstdatacol
) - 1)
2236 (void) raidz_parity_verify(zio
, rm
);
2239 * We're here because either:
2241 * total_errors == rm_first_datacol, or
2242 * vdev_raidz_combrec() failed
2244 * In either case, there is enough bad data to prevent
2247 * Start checksum ereports for all children which haven't
2248 * failed, and the IO wasn't speculative.
2250 zio
->io_error
= SET_ERROR(ECKSUM
);
2252 if (!(zio
->io_flags
& ZIO_FLAG_SPECULATIVE
)) {
2253 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2254 rc
= &rm
->rm_col
[c
];
2255 if (rc
->rc_error
== 0) {
2256 zio_bad_cksum_t zbc
;
2257 zbc
.zbc_has_cksum
= 0;
2259 rm
->rm_ecksuminjected
;
2261 zfs_ereport_start_checksum(
2263 vd
->vdev_child
[rc
->rc_devidx
],
2264 zio
, rc
->rc_offset
, rc
->rc_size
,
2265 (void *)(uintptr_t)c
, &zbc
);
2272 zio_checksum_verified(zio
);
2274 if (zio
->io_error
== 0 && spa_writeable(zio
->io_spa
) &&
2275 (unexpected_errors
|| (zio
->io_flags
& ZIO_FLAG_RESILVER
))) {
2277 * Use the good data we have in hand to repair damaged children.
2279 for (c
= 0; c
< rm
->rm_cols
; c
++) {
2280 rc
= &rm
->rm_col
[c
];
2281 cvd
= vd
->vdev_child
[rc
->rc_devidx
];
2283 if (rc
->rc_error
== 0)
2286 zio_nowait(zio_vdev_child_io(zio
, NULL
, cvd
,
2287 rc
->rc_offset
, rc
->rc_abd
, rc
->rc_size
,
2288 ZIO_TYPE_WRITE
, ZIO_PRIORITY_ASYNC_WRITE
,
2289 ZIO_FLAG_IO_REPAIR
| (unexpected_errors
?
2290 ZIO_FLAG_SELF_HEAL
: 0), NULL
, NULL
));
2296 vdev_raidz_state_change(vdev_t
*vd
, int faulted
, int degraded
)
2298 if (faulted
> vd
->vdev_nparity
)
2299 vdev_set_state(vd
, B_FALSE
, VDEV_STATE_CANT_OPEN
,
2300 VDEV_AUX_NO_REPLICAS
);
2301 else if (degraded
+ faulted
!= 0)
2302 vdev_set_state(vd
, B_FALSE
, VDEV_STATE_DEGRADED
, VDEV_AUX_NONE
);
2304 vdev_set_state(vd
, B_FALSE
, VDEV_STATE_HEALTHY
, VDEV_AUX_NONE
);
2307 vdev_ops_t vdev_raidz_ops
= {
2311 vdev_raidz_io_start
,
2313 vdev_raidz_state_change
,
2316 VDEV_TYPE_RAIDZ
, /* name of this vdev type */
2317 B_FALSE
/* not a leaf vdev */